记录编号	616847	评测结果	AAAAAAAAAA
题目名称	3338.[SCOI 2016]美味	最终得分	100
用户昵称	2_16鸡扒拌面	是否通过	通过
代码语言	C++	运行时间	5.583 s
提交时间	2026-07-01 15:39:16	内存使用	48.71 MiB

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,V=1<<18;

int n,m,tot;
int a[N],rt[N];
struct T{int ls,rs,cnt;}tr[N*20];

void insert(int &p,int q,int l,int r,int x){
    p=++tot;
    tr[p]=tr[q];
    tr[p].cnt++;
    if(l==r)return;
    int m=(l+r)>>1;
    if(x<=m)insert(tr[p].ls,tr[q].ls,l,m,x);
    else insert(tr[p].rs,tr[q].rs,m+1,r,x);
}

int query(int p,int q,int l,int r,int L,int R){
    if(L>r||R<l)return 0;
    if(L<=l&&r<=R)return tr[p].cnt-tr[q].cnt;
    int m=(l+r)>>1;
    return query(tr[p].ls,tr[q].ls,l,m,L,R)+query(tr[p].rs,tr[q].rs,m+1,r,L,R);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    int mx=0;
    for(int i=1;i<=n;i++){cin>>a[i];mx=max(mx,a[i]);}
    int MAXV=262143;
    for(int i=1;i<=n;i++)insert(rt[i],rt[i-1],0,MAXV,a[i]);
    while(m--){
        int b,x,l,r;
        cin>>b>>x>>l>>r;
        int cur=0;
        for(int k=17;k>=0;k--){
            int bit=(b>>k)&1;
            int want=bit^1;
            int tmp=cur|(want<<k);
            int L=max(0,tmp-x);
            int R=min(MAXV,tmp+(1<<k)-1-x);
            if(L<=R&&query(rt[r],rt[l-1],0,MAXV,L,R)>0)cur=tmp;
            else cur|=bit<<k;
        }
        cout<<(b^cur)<<"\n";
    }
    return 0;
}