【BZOJ3489】A simple rmq problem【kd树】

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #include <iostream>
  5 
  6 using namespace std;
  7 const int maxn=1e5+100;
  8 const int INF=2147000000;
  9 int a[maxn],pre[maxn],nxt[maxn],last[maxn];
 10 struct kdNode{
 11     int x[3],mnn[3],mxn[3];
 12     int lc,rc;
 13     int val,maxv;
 14 }p[maxn],q;
 15 int n,m,cmpNo,root;
 16 int cmp(kdNode a,kdNode b){
 17     return a.x[cmpNo]<b.x[cmpNo];
 18 }
 19 void maintain(int o){
 20     int l=p[o].lc,r=p[o].rc;
 21     for(int i=0;i<3;i++){
 22         p[o].mnn[i]=min(min(p[l].mnn[i],p[r].mnn[i]),p[o].x[i]);
 23         p[o].mxn[i]=max(max(p[l].mxn[i],p[r].mxn[i]),p[o].x[i]);
 24     }
 25     p[o].maxv=max(max(p[l].maxv,p[r].maxv),p[o].val);
 26 }
 27 void build(int&o,int l,int r,int d){
 28     if(l>r){
 29         o=0;
 30         return;
 31     }
 32     int m=l+(r-l)/2;
 33     cmpNo=d,o=m;
 34     nth_element(p+l,p+m,p+r+1,cmp);
 35     build(p[o].lc,l,m-1,(d+1)%3);
 36     build(p[o].rc,m+1,r,(d+1)%3);
 37     maintain(o);
 38 }
 39 int ans,l,r;//查询l<=x[0]<=r,x[1]<=l,x[2]>=r 空间内的最大值，这时候的kd树感觉就是高维线段树
 40 bool all(int o){
 41     if(p[o].mxn[0]<=r&&p[o].mnn[0]>=l&&p[o].mxn[1]<l&&p[o].mnn[2]>r)
 42         return true;
 43     return false;
 44 }
 45 bool have(int o){
 46     if(p[o].mnn[0]<=r&&p[o].mxn[0]>=l&&p[o].mnn[1]<l&&p[o].mxn[2]>r)
 47         return true;
 48     return false;
 49 }
 50 
 51 void query(int o,int d){
 52     if(!o){
 53         return;
 54     }
 55     if(all(o)){
 56         ans=max(ans,p[o].maxv);
 57         return;
 58     }
 59   //  ans=max(ans,p[o].val);
 60     if(p[o].x[0]<=r&&p[o].x[0]>=l&&p[o].x[1]<l&&p[o].x[2]>r)
 61         ans=max(ans,p[o].val);
 62 
 63     int lc=p[o].lc,rc=p[o].rc;
 64     if(p[lc].maxv<p[rc].maxv){
 65         if(all(rc)){
 66             ans=max(ans,p[rc].maxv);
 67         }else if(have(rc)){
 68             query(rc,(d+1)%3);
 69         }
 70         if(ans<p[lc].maxv){
 71             if(all(lc))
 72                 ans=max(ans,p[lc].maxv);
 73             else if(have(lc))
 74                 query(lc,(d+1)%3);
 75         }
 76     }else{
 77         if(all(lc)){
 78             ans=max(ans,p[lc].maxv);
 79         }else if(have(lc)){
 80             query(lc,(d+1)%3);
 81         }
 82         if(ans<p[rc].maxv){
 83             if(all(rc))
 84                 ans=max(ans,p[rc].maxv);
 85             else if(have(rc))
 86                 query(rc,(d+1)%3);
 87         }
 88     }
 89 }
 90 
 91 int main(){
 92     scanf("%d%d",&n,&m);
 93     for(int i=1;i<=n;i++){
 94         scanf("%d",&a[i]);
 95         if(last[a[i]])
 96             pre[i]=last[a[i]];
 97         else
 98             pre[i]=0;
 99         last[a[i]]=i;
100     }
101     memset(last,0,sizeof(last));
102     for(int i=n;i>=1;i--){
103         if(last[a[i]])
104             nxt[i]=last[a[i]];
105         else
106             nxt[i]=n+1;
107         last[a[i]]=i;
108     }
109 
110     for(int i=1;i<=n;i++){
111         p[i].x[0]=i;
112         p[i].x[1]=pre[i];
113         p[i].x[2]=nxt[i];
114         p[i].val=a[i];
115         //printf("%d %d %d\n",p[i].x[0],p[i].x[1],p[i].x[2]);
116     }
117     for(int i=0;i<3;i++){
118         p[0].mnn[i]=INF;
119         p[0].mxn[i]=-INF;
120     }
121 
122     build(root,1,n,0);
123     int lastans=0;
124     for(int i=1;i<=m;i++){
125         int L,R;
126         scanf("%d%d",&L,&R);
127         l=min((L+lastans)%n+1,(R+lastans)%n+1);
128         r=max((L+lastans)%n+1,(R+lastans)%n+1);
129        // printf("%d %d\n",l,r);
130         ans=0;
131         query(root,0);
132         printf("%d\n",ans);
133         lastans=ans;
134     }
135 return 0;
136 }