自认为是一道思想很妙的题。
直接分析问题。
如果没有xxx的干扰直接上可持久化01trie01trie01trie走人。
但现在有了xxx这个偏移量。
相当于把整个01trie01trie01trie向左平移了xxx。
这个感觉01trie01trie01trie维护不是很可做。
于是我们把可持久化01trie01trie01trie转成主席树。
发现只是把选择左/右子树变成了选择左/右半区间。
然后照样贪心查询就行了。
代码:
#include<bits/stdc++.h>#define N 200005#define M 100005#define P 17using namespace std;inline int read(){int ans=0;char ch=getchar();while(!isdigit(ch))ch=getchar();while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();return ans;}int rt[N],son[N*30][2],siz[N*30],n,m,a[N],tot=0;inline void update(int&p,int las,int l,int r,int k){p=++tot,son[p][0]=son[las][0],son[p][1]=son[las][1],siz[p]=siz[las]+1;if(l==r)return;int mid=l+r>>1;if(k<=mid)update(son[p][0],son[las][0],l,mid,k);else update(son[p][1],son[las][1],mid+1,r,k);}inline int query(int pl,int pr,int l,int r,int ql,int qr){if(ql>r||qr<l)return 0;if(ql<=l&&r<=qr)return siz[pr]-siz[pl];int mid=l+r>>1;if(qr<=mid)return query(son[pl][0],son[pr][0],l,mid,ql,qr);if(ql>mid)return query(son[pl][1],son[pr][1],mid+1,r,ql,qr);return query(son[pl][0],son[pr][0],l,mid,ql,mid)+query(son[pl][1],son[pr][1],mid+1,r,mid+1,qr);}inline int query(int l,int r,int val,int dta){int ret=0,xortmp=0;for(int i=P;~i;--i){int tmp=1<<i;if(val&tmp)if(query(rt[l-1],rt[r],1,200000,xortmp-dta,xortmp+tmp-dta-1))ret|=tmp;else xortmp|=tmp;else if(query(rt[l-1],rt[r],1,200000,xortmp+tmp-dta,xortmp+tmp*2-dta-1))ret|=tmp,xortmp|=tmp;}return ret;}int main(){n=read(),m=read();for(int i=1;i<=n;++i)update(rt[i],rt[i-1],1,200000,(a[i]=read()));for(int i=1,b,x,l,r;i<=m;++i)b=read(),x=read(),l=read(),r=read(),printf("%d\n",query(l,r,b,x));return 0;}