trie 树思想运用到主席树上orz
#include <iostream>
#include <cstdio>
using namespace std;
int n, m, a[200005], cnt, rot[200005], bb, xx, uu, vv;
struct Node{
int l, r, sum;
}nd[5000005];
int build(int l, int r){
int o=++cnt;
if(l==r) ;
else{
int mid=(l+r)>>1;
nd[o].l = build(l, mid);
nd[o].r = build(mid+1, r);
}
return o;
}
int update(int o, int l, int r, int x){
int re=++cnt;
nd[re] = nd[o];
nd[re].sum++;
if(l==r) ;
else{
int mid=(l+r)>>1;
if(x<=mid) nd[re].l = update(nd[o].l, l, mid, x);
else nd[re].r = update(nd[re].r, mid+1, r, x);
}
return re;
}
bool query(int p, int o, int l, int r, int x, int y){
if(x>y) return 0;
if(l>=x && r<=y) return nd[o].sum-nd[p].sum>0;
else{
int mid=(l+r)>>1;
bool fla=false;
if(x<=mid) fla |= query(nd[p].l, nd[o].l, l, mid, x, y);
if(mid<y) fla |= query(nd[p].r, nd[o].r, mid+1, r, x, y);
return fla;
}
}
int main(){
cin>>n>>m;
rot[0] = build(0, 100000);
for(int i=1; i<=n; i++){
scanf("%d", &a[i]);
rot[i] = update(rot[i-1], 0, 100000, a[i]);
}
while(m--){
scanf("%d %d %d %d", &bb, &xx, &uu, &vv);
int ans=0;
for(int i=17; i>=0; i--){
int now=ans+((bb&(1<<i))^(1<<i));
int nowr=now+(1<<i)-1;
if(query(rot[uu-1], rot[vv], 0, 100000, max(now-xx,0), min(nowr-xx,100000))) ans = now;
else ans += bb&(1<<i);
}
printf("%d\n", ans^bb);
}
return 0;
}