这道题其实也是最大异或和，我们只需要把后面的加发看作整体之后进行按位贪心
这样答案区间就是一段区间，因此可以用主席树来维护
#include<bits/stdc++.h> #define getsz(p) (p?p->sz:0) using namespace std; typedef long long ll; const int mod=1e9+7; const int N=3e5+10; int a[N]; struct node{ int l,r; int sz; node *ls,*rs; }*rt[N],pool[N*30]; int idx; node *copynode(node *rt){ node *p=pool+(++idx); pool[idx]=*rt; return p; } node *insert(node *rt,int l,int r,int x){ node *p; if(rt) p=copynode(rt); else{ p=pool+(++idx); p->l=l,p->r=r; } ++p->sz; if(p->l==p->r) return p; int mid=l+r>>1; if(x<=mid) p->ls=insert(p->ls,l,mid,x); else p->rs=insert(p->rs,mid+1,r,x); return p; } int query(node* p,int x){ if(x < 0) return 0; if(!p) return 0; if(p->r <= x) return p->sz; int mid = (p->l + p->r)/2; if(x <= mid) return query(p->ls, x); else return getsz(p->ls) + query(p->rs,x); } int main(){ ios::sync_with_stdio(false); int n,m; cin>>n>>m; int i; int x=100000; for(i=1;i<=n;i++){ cin>>a[i]; rt[i]=insert(rt[i-1],1,x,a[i]); } int b,l,r; while(m--){ cin>>b>>x>>l>>r; int ans = 0; for(int i=20;i>=0;i--){ if((b>>i)&1){ n = query(rt[r], ans-x+(1<<i)-1) - query(rt[r], ans-x-1); n -= query(rt[l-1], ans-x+(1<<i)-1) - query(rt[l-1], ans-x-1); if(n==0) ans += (1<<i); } else{ n = query(rt[r], ans-x+(1<<(i+1))-1) - query(rt[r], ans-x+(1<<i)-1); n -= query(rt[l-1], ans-x+(1<<(i+1))-1) - query(rt[l-1],ans-x+(1<<i)-1); if(n) ans += (1<<i); } } cout<<(ans^b)<<endl; } return 0; }