数据结构

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long 
 4 #define N 100005
 5 struct trie
 6 {
 7     int nn,sz[N*20],ch[N*20][2];
 8     void ins(int &x,int y,int p,int d)
 9     {
10         sz[x=++nn]=sz[y]+1;
11         if(d==-1)return;
12         int t=p>>d&1;ch[x][t^1]=ch[y][t^1];
13         ins(ch[x][t],ch[y][t],p,d-1);
14     }
15     int qry(int x,int y,int p,int d)
16     {
17         if(d==-1)return 0;
18         int t=p>>d&1;
19         if(sz[ch[y][t^1]]-sz[ch[x][t^1]])return qry(ch[x][t^1],ch[y][t^1],p,d-1)|(1<<d);
20         else return qry(ch[x][t],ch[y][t],p,d-1);
21     }
22 }T;
23 struct k1{int l,r,x,tl,tr;}qq[N];
24 struct k2{int s,v,t;}q[N<<2],q1[N<<2],q2[N<<2];
25 bool cmp(k2 a,k2 b){return a.s<b.s;}
26 vector<int>g[N<<2];
27 void upd(int x,int l,int r,int tl,int tr,int v)
28 {
29     if(tl>tr)return;
30     if(tl<=l&&r<=tr){g[x].push_back(v);return;}
31     int mid=l+r>>1;
32     if(tl<=mid)upd(x<<1,l,mid,tl,tr,v);
33     if(tr>mid)upd(x<<1|1,mid+1,r,tl,tr,v);
34 } 
35 int cc,tt,tp,rt[N],ans[N],st[N];
36 void calc(int x,int tl,int tr)
37 {
38     tp=T.nn=0;
39     for(int i=tl;i<=tr;i++)
40     {
41         st[++tp]=q[i].s;
42         T.ins(rt[tp],rt[tp-1],q[i].v,17);
43     }
44     for(int i=0;i<g[x].size();i++)
45     {
46         int p=g[x][i],l=upper_bound(st+1,st+tp+1,qq[p].l-1)-st-1,r=upper_bound(st+1,st+tp+1,qq[p].r)-st-1;
47         ans[p]=max(ans[p],T.qry(rt[r],rt[l],qq[p].x,17));
48     }
49 }
50 void sol(int x,int l,int r,int tl,int tr)
51 {
52     if(tl>tr)return;
53     calc(x,tl,tr);
54     if(l==r)return;
55     int mid=l+r>>1,t1=0,t2=0;
56     for(int i=tl;i<=tr;i++)if(q[i].t<=mid)q1[++t1]=q[i];else q2[++t2]=q[i];
57     for(int i=1;i<=t1;i++)q[tl+i-1]=q1[i];
58     for(int i=1;i<=t2;i++)q[tl+t1+i-1]=q2[i];
59     sol(x<<1,l,mid,tl,tl+t1-1);sol(x<<1|1,mid+1,r,tl+t1,tr);
60 }
61 int main()
62 {
63     int n,m;
64     scanf("%d%d",&n,&m);
65     for(int i=1,x;i<=n;i++)scanf("%d",&x),T.ins(rt[i],rt[i-1],x,17);
66     for(int i=1,a,b,c,d,o;i<=m;i++)
67     {
68         scanf("%d%d%d",&o,&a,&b);
69         if(!o)cc++,q[cc]=(k2){a,b,cc};
70         else{scanf("%d%d",&c,&d);qq[++tt]=(k1){a,b,c,max(1,cc-d+1),cc};ans[tt]=T.qry(rt[a-1],rt[b],c,17);}
71     }
72     for(int i=1;i<=tt;i++)upd(1,1,cc,qq[i].tl,qq[i].tr,i);
73      sort(q+1,q+cc+1,cmp);sol(1,1,cc,1,cc);
74     for(int i=1;i<=tt;i++)printf("%d
",ans[i]);
75     return 0;
76 }