[BZOJ4137]火星商店问题

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<vector>
  5 #include<cstring>
  6 #define M 100010
  7 #define ls node<<1
  8 #define rs node<<1|1
  9 using namespace std;
 10 
 11 int n,m,cnt,cnt1,cnt2;
 12 int rt[M],f[M],ans[M];
 13 vector<int>seg[M<<2];
 14 struct CG{int s,v,t;}q[M],tmp1[M],tmp2[M];
 15 struct ASK{int l,r,l1,r1,x;}p[M];
 16 bool cmp(CG a1,CG a2) {return a1.s<a2.s;}
 17 
 18 struct Trie
 19 {
 20     int cnt;
 21     int val[M<<5],ch[M<<5][2];
 22     void insert(int &now,int pre,int w,int o)
 23     {
 24         
 25         now=++cnt,val[now]=val[pre]+1;
 26         ch[now][0]=ch[pre][0];ch[now][1]=ch[pre][1];
 27         if(o==-1) return;bool c=w&(1<<o);
 28         insert(ch[now][c],ch[pre][c],w,o-1);
 29     }
 30     int query(int now,int pre,int w,int o)
 31     {
 32         if(o==-1) return 0;
 33         bool c=w&(1<<o);
 34         int tmp=val[ch[now][c^1]]-val[ch[pre][c^1]];
 35         if(tmp) return query(ch[now][c^1],ch[pre][c^1],w,o-1)+(1<<o);
 36         else return query(ch[now][c],ch[pre][c],w,o-1);
 37     }
 38 }T;
 39 
 40 void insert(int node,int l,int r,int l1,int r1,int id)
 41 {
 42     if(l1>r1) return;
 43     if(l1<=l&&r1>=r) {seg[node].push_back(id);return;}
 44     int mid=(l+r)/2;
 45     if(l1<=mid) insert(ls,l,mid,l1,r1,id);
 46     if(r1>mid) insert(rs,mid+1,r,l1,r1,id);
 47 }
 48 
 49 int get(int v)
 50 {
 51     int l=1,r=cnt,ans=0;
 52     while(l<=r)
 53     {
 54         int mid=(l+r)/2;
 55         if(f[mid]<=v) ans=mid,l=mid+1;
 56         else r=mid-1;
 57     }
 58     return ans;
 59 }
 60 
 61 void cal(int node,int l,int r)
 62 {
 63     cnt=T.cnt=0;
 64     for(int i=l;i<=r;i++)
 65     {
 66         f[++cnt]=q[i].s;
 67         T.insert(rt[cnt],rt[cnt-1],q[i].v,17);
 68     }
 69     for(int i=0;i<seg[node].size();i++)
 70     {
 71         int id=seg[node][i];
 72         int l=get(p[id].l-1);
 73         int r=get(p[id].r);
 74         ans[id]=max(ans[id],T.query(rt[r],rt[l],p[id].x,17));
 75     }
 76 }
 77 
 78 void solve(int node,int l,int r,int l1,int r1)
 79 {
 80     if(l1>r1) return;
 81     cal(node,l,r);
 82     if(l==r) return;
 83     int mid=(l+r)/2,t1=0,t2=0;
 84     for(int i=l1;i<=r1;i++)
 85     {
 86         if(q[i].t<=mid) tmp1[++t1]=q[i];
 87         else tmp2[++t2]=q[i];
 88     }
 89     for(int i=1;i<=t1;i++) q[i+l1-1]=tmp1[i];
 90     for(int i=1;i<=t2;i++) q[i+l1-1+t1]=tmp2[i];
 91     solve(ls,l,mid,l1,l1+t1-1);
 92     solve(rs,mid+1,r,l1+t1,r1);
 93 }
 94 
 95 int main()
 96 {
 97     scanf("%d%d",&n,&m);
 98     for(int i=1;i<=n;i++) 
 99     {
100         int x;scanf("%d",&x);
101         T.insert(rt[i],rt[i-1],x,17);
102     }
103     for(int i=1;i<=m;i++)
104     {
105         int opt;scanf("%d",&opt);
106         if(!opt)
107         {
108             int s,v;scanf("%d%d",&s,&v);
109             cnt1++;q[cnt1]=(CG){s,v,cnt1};
110         }
111         else
112         {
113             int l,r,x,d;scanf("%d%d%d%d",&l,&r,&x,&d);
114             ans[++cnt2]=T.query(rt[r],rt[l-1],x,17);
115             p[cnt2]=(ASK){l,r,max(1,cnt1-d+1),cnt1,x};
116         }
117     }
118     for(int i=1;i<=cnt2;i++) 
119         insert(1,1,cnt1,p[i].l1,p[i].r1,i);
120     sort(q+1,q+1+cnt1,cmp);
121     solve(1,1,cnt1,1,cnt1);
122     for(int i=1;i<=cnt2;i++) printf("%d\n",ans[i]);
123     return 0;
124 }