注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ3489]A simple rmq problem(k-d tree)  

2015-05-02 14:18:23|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3489: A simple rmq problem

Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 517  Solved: 160
[Submit][Status][Discuss]

Description

因为是OJ上的题,就简单点好了。给出一个长度为n的序列,给出M个询问:在[l,r]之间找到一个在这个区间里只出现过一次的数,并且要求找的这个数尽可能大。如果找不到这样的数,则直接输出0。我会采取一些措施强制在线。

Input

第一行为两个整数N,MM是询问数,N是序列的长度(N<=100000M<=200000)

第二行为N个整数,描述这个序列{ai},其中所有1<=ai<=N

再下面M行,每行两个整数xy

询问区间[l,r]由下列规则产生(OIER都知道是怎样的吧>_<)

l=min(x+lastans)mod n+1,(y+lastansmod n+1);

r=max(x+lastans)mod n+1,(y+lastansmod n+1);

Lastans表示上一个询问的答案,一开始lastans0

Output

一共M行,每行给出每个询问的答案。

Sample Input

10 10 6 4 9 10 9 10 9 4 10 4 3 8 10 1 3 4 9 4 8 1 7 8 2 9 1 1 7 3 9 9

Sample Output

4 10 10 0 0 10 0 4 0 4

HINT

注意出题人为了方便,input的第二行最后多了个空格。

Source

Solution

国冬上听说kdtree可以写传统数据结构题顿时惊呆了

记录每个位置的数前一次出现的位置pre[i]和后一次出现的位置nxt[i],然后我们询问的就是

1. l<=i<=r

2. pre[i]<l

3. nxt[i]>r

满足三个条件下的max(a[i])

将每个点的信息看作三维空间上带权值的点(i,pre[i],nxt[i]),然后建立kdtree。

询问的话,等价于第一维在[l,r]范围内,第二维在[0,l-1]范围内,第三维在[r+1,+oo]范围内的一个三维空间内,查询在里面的点权最大值。于是这样就能转换成kdtree啦~

关于kdtree:

1. 建树跟二维的一样建法,xyz三个坐标轮流换,并且维护当前域内的点权max

2. 查询的时候,如果当前域内max<=ans,直接不做(剪枝1),如果当前点在查询域内则更新答案,如果子空间与查询域不交则不查(剪枝2)(好像一坨都是废话。。。)

然后我们就可以用理论上是O(n^(5/3))的复杂度跑过一些O(nlog^2)的算法了

跑得比可持久化树套树快到不知道哪里去了。。。而且代码短好多。。。

Code

/**************************************************************
    Problem: 3489
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:4532 ms
    Memory:8624 kb
****************************************************************/
 
#include<cstdio>
#include<algorithm>
#define N 100010
int n,m,a[N],i,j,l,r,D,pos[3][2],las[N],L[N],R[N],rt,ans;
struct T{int d[3],s[2],min[3],max[3],w;}t[N];
struct P{int d[3],w;}p[N];
bool operator<(const P&a,const P&b){return a.d[D]<b.d[D];}
#define ls t[now].s[0]
#define rs t[now].s[1]
#define cmax(a,b) (a<b?a=b:a)
#define cmin(a,b) (a>b?a=b:a)
void mt(int o,int s){
    for(int i=0;i<3;i++)
    cmin(t[o].min[i],t[s].min[i]),
    cmax(t[o].max[i],t[s].max[i]);
    cmax(t[o].w,t[s].w);
}
int bt(int l,int r,int d){
    D=d;int now=l+r>>1;
    std::nth_element(p+l,p+now,p+r+1);t[now].w=p[now].w;
    for(int i=0;i<3;i++)t[now].d[i]=t[now].min[i]=t[now].max[i]=p[now].d[i];
    if(l<now)ls=bt(l,now-1,(d+1)%3),mt(now,ls);
    if(now<r)rs=bt(now+1,r,(d+1)%3),mt(now,rs);
    return now;
}
bool check(int now){
    for(int i=0;i<3;i++)
    if(pos[i][0]>t[now].max[i]||pos[i][1]<t[now].min[i])return 0;
    return 1;
}
void query(int now){
    if(t[now].w<ans)return;bool flag=1;
    for(int i=0;i<3;i++)
    if(pos[i][0]>t[now].min[i]||t[now].max[i]>pos[i][1])flag=0;
    if(flag){cmax(ans,t[now].w);return;}flag=1;
    for(int i=0;i<3;i++)
    if(pos[i][0]>p[now].d[i]||pos[i][1]<p[now].d[i])flag=0;
    if(flag)cmax(ans,p[now].w);
    if(ls&&check(ls))query(ls);
    if(rs&&check(rs))query(rs);
}
int aa;char ch;int F(){
    while(ch=getchar(),ch<'0'||ch>'9');aa=ch-'0';
    while(ch=getchar(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return aa;
}
int main(){
    for(n=F(),m=F(),i=1;i<=n;i++)L[i]=las[a[i]=F()],las[a[i]]=i;
    for(i=0;i<=n;i++)las[i]=n+1;
    for(i=n;i;i--)R[i]=las[a[i]],las[a[i]]=i;
    for(i=1;i<=n;i++)p[i]=(P){i,L[i],R[i],a[i]};
    for(rt=bt(1,n,0);m--;query(rt),printf("%d\n",ans)){
        l=(F()+ans)%n+1,r=(F()+ans)%n+1;
        if(l>r)ans=l,l=r,r=ans;ans=0;
        pos[0][0]=l,pos[0][1]=r;
        pos[1][0]=0,pos[1][1]=l-1;
        pos[2][0]=r+1,pos[2][1]=n+1;
    }
}
  评论这张
 
阅读(380)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018