题解 P3293 【[SCOI2016]美味】

# 主席树 感觉其他关于主席树题解不是很好懂？那我来一发 ------------ # 思路： 首先，我们看到要选区间的数，并且结合题意就知道用主席树啦~~(看题目标签也阔以QAQ)~~ 然后我们看到要求最大异或和，因为异或中，二进制每一位都是独立的，所以我们考虑按位处理 而题目是给定两个数$b,x$，要求$(a[i]+x)\oplus b$，那么既然$b,x$给定了，我们只需要维护一下$a[i]$就行了 于是，我们开一颗主席树，以$a[i]$为下标，里面存的值表示出现次数 - 那么我们考虑下面的情况： 首先，我们根据贪心思路，我们从高到低一位一位来看，显然如果可以让当前这一位为$1$，那么肯定会更优（不管对后面的影响） 那么我们分两类讨论（$ans$记录的是$a[i]+x$,主席树如上文所述）： - 假设现在我们处理到了第$i$位，如果此时$b$这一位为$0$，那么我们为了最终$ans\oplus b$更大，$ans$最好在这一位为$1$，那么$ans$的范围多少呢？ 其实就是$[ans+(1<<i),ans+(1<<(i+1))-1]$ 为什么呢？ 举个例子，假设枚举到了第$4$位，最右边为最低位，此时的$ans$为$1010000$,因为只枚举到了第四位，所以第五位之后都是$0$，那么为了让第四位是$1$，那么范围就是$[1011000,1011111]$ 而我们知道了$ans$的范围，而$ans$代表的是$a[i]+x$，那么我们其实只需要知道有没有$a[i]$在$[ans+(1<<i)-x,ans+(1<<(i+1))-1-x]$这个区间就可以了，而题目中限制了在某个区间中，直接上主席树板子查询就$ok$ - 那么如果$b$此时为$1$的话同理，那么我们为了最终$ans\oplus b$更大，$ans$这一位最好为$0$，那么$ans$的取值范围是$[ans,ans+(1<<i)-1]$,自然$a[i]$的取值范围就是$[ans-x,ans+(1<<i)-1-x]$了 最后把$ans$异或一下$b$就是答案啦 ------------ 下面是美滋滋的代码时间~~~ ~~~cpp #include<iostream> #include<cstdio> #include<cstring> #define N 200007 #define M 100007 using namespace std; struct Tree { int ls,rs,sum; }tr[N<<7]; int n,m,cnt; int root[N]; void Pushup(int rt) { tr[rt].sum=tr[tr[rt].ls].sum+tr[tr[rt].rs].sum; } void Build(int &rt,int l,int r) { if(!rt) rt=++cnt; if(l==r) return; int mid=l+((r-l)>>1); Build(tr[rt].ls,l,mid); Build(tr[rt].rs,mid+1,r); } void Insert(int &now,int last,int l,int r,int pos) { if(!now) now=++cnt; if(l==r) { tr[now].sum=tr[last].sum+1; return; } int mid=l+((r-l)>>1); if(pos<=mid) { tr[now].rs=tr[last].rs; Insert(tr[now].ls,tr[last].ls,l,mid,pos); } else { tr[now].ls=tr[last].ls; Insert(tr[now].rs,tr[last].rs,mid+1,r,pos); } Pushup(now); } bool Search(int now,int last,int l,int r,int ql,int qr) { if(tr[last].sum-tr[now].sum<1) return 0; if(ql<=l&&r<=qr) return 1; int mid=l+((r-l)>>1),tot=0; if(ql<=mid) tot+=Search(tr[now].ls,tr[last].ls,l,mid,ql,qr); if(qr>mid) tot+=Search(tr[now].rs,tr[last].rs,mid+1,r,ql,qr); return tot; } int main() { scanf("%d%d",&n,&m); Build(root[0],0,M); for(int i=1;i<=n;++i) { int in; scanf("%d",&in); Insert(root[i],root[i-1],0,M,in); } for(int i=1;i<=m;++i) { int b,x,ql,qr,ans=0; scanf("%d%d%d%d",&b,&x,&ql,&qr); for(int j=17;j>=0;--j) { int L,R,opt; if(b&(1<<j)) L=ans,R=ans+((1<<j)-1),opt=0; else L=ans+(1<<j),R=ans+((1<<(j+1))-1),opt=1; //printf("\n-------test-------\n"),printf("ans:%d",opt),printf("\n-------test-------\n"); if(!Search(root[ql-1],root[qr],0,M,max(L-x,0),min(R-x,M))) opt^=1; ans+=(opt<<j); } printf("%d\n",ans^b); } return 0; } ~~~