https://www.lydsy.com/JudgeOnline/problem.php?id=4571
https://www.luogu.org/problemnew/show/P3293
一家餐厅有 n 道菜，编号 1...n ，大家对第 i 道菜的评价值为 ai(1<=i<=n)。有 m 位顾客，第 i 位顾客的期望值为 bi，而他的偏好值为 xi 。因此，第 i 位顾客认为第 j 道菜的美味度为 bi XOR (aj+xi)，XOR 表示异或运算。
第 i 位顾客希望从这些菜中挑出他认为最美味的菜，即美味值最大的菜，但由于价格等因素，他只能从第 li 道到第 ri 道中选择。请你帮助他们找出最美味的菜。
打眼一看，太好了！洛谷试炼场的可持久化trie终于是一道真的可持久化trie了！
等等，怎么还能加x的，emmm……
于是将自己的板子推倒重来，我们不用以前（我写的）板子造trie，而是使用值域来造可持久化trie树。
（但其实建法都差不多……开始怀疑以前的做法是否能够搬过来。）
这样就变成了对于b的每一位（当然是贪心地从高到低），我们查找符合条件的值域-x后是否存在这一位异或后为1即可。
（反正我理解的时候都是看的代码理解的，感觉说起原理来很绕，相信大家一定能看代码理解的233）
#include<cmath> #include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int N=2e5+5; const int mx=1e5-1; inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X; } struct trie{ int a[2],sz; }tr[N*20]; int tot,rt[N],pool,n,m; void insert(int y,int &x,int l,int r,int k){ tr[x=++pool]=tr[y]; tr[x].sz++; if(l==r)return; int mid=(l+r)>>1; if(k<=mid)insert(tr[y].a[0],tr[x].a[0],l,mid,k); else insert(tr[y].a[1],tr[x].a[1],mid+1,r,k); return; } int query(int nl,int nr,int l,int r,int L,int R){ if(l==L&&r==R)return tr[nr].sz-tr[nl].sz; int mid=(l+r)>>1; if(R<=mid)return query(tr[nl].a[0],tr[nr].a[0],l,mid,L,R); else if(L>mid)return query(tr[nl].a[1],tr[nr].a[1],mid+1,r,L,R); else return query(tr[nl].a[0],tr[nr].a[0],l,mid,L,mid)+ query(tr[nl].a[1],tr[nr].a[1],mid+1,r,mid+1,R); } int ask(int l,int r,int k,int x){ int ans=0; for(int i=18;i>=0;i--){ int L,R; bool p=k&(1<<i); if(p)L=ans,R=ans+(1<<i)-1; else L=ans+(1<<i),R=ans+(1<<i+1)-1; L=max(L-x,0),R=min(R-x,mx); if(L<=R&&query(rt[l-1],rt[r],0,mx,L,R))ans+=(1<<i)*(p^1); else ans+=(1<<i)*p; } return ans^k; } int main(){ n=read(),m=read(); for(int i=1;i<=n;i++){ insert(rt[i-1],rt[i],0,mx,read()); } for(int i=1;i<=m;i++){ int k=read(),x=read(),l=read(),r=read(); printf("%d ",ask(l,r,k,x)); } return 0; }
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++