题解 P3293 【[SCOI2016]美味】

本题为经典的可持久化trie练习题 先对所有菜建一棵可持久化trie 顾客的偏好值相当于在trie上的“偏移量”，需要支持一个查询操作：查询两个版本间trie上数值L~R区间是否存在菜 查询的时候将r版本和l-1版本trie相减，在trie上跑一遍类似线段树的查询就好 最后对于每个顾客，跑一下带偏移的按位贪心，也就是贪到每一层时，分别用上面的操作查询出L-x~mid-x区间和mid-x+1~R-x区间分别是否存在菜。 复杂度貌似是 $ O ( m log^2 \cdot n ) $ ？ 良心提示：在bzoj上不要用cin。。RE了我好久 贴代码 ```cpp #include<iostream> #include<algorithm> #include<cstdio> using namespace std; const int MAXN=524287; struct node { int cnt; node *ls,*rs; }pool[6000010],*root[2*MAXN]; int top,curt; int n,m,a,b,x,l,r; void inorder(node *cur) { printf("{"); if(cur->ls){inorder(cur->ls);} printf("(%d)",cur->cnt); if(cur->rs){inorder(cur->rs);} printf("}"); } node* bt(int l,int r) { node *tmp=&pool[top++]; tmp->cnt=0; if(l!=r) { int m=(l+r)/2; tmp->ls=bt(l,m); tmp->rs=bt(m+1,r); } return tmp; } node* Change(node *pre,int x,int l,int r) { node *tmp=&pool[top++]; tmp->cnt=pre->cnt+1; if(l==r){return tmp;} int m=(l+r)/2; if(x<=m){tmp->ls=Change(pre->ls,x,l,m);tmp->rs=pre->rs;} else {tmp->ls=pre->ls;tmp->rs=Change(pre->rs,x,m+1,r);} return tmp; } bool hn(node *cur,node *sub,int l,int r,int lrg,int rrg) { if(l==lrg&&r==rrg)return cur->cnt-sub->cnt; int m=(l+r)/2; if(rrg<=m)return hn(cur->ls,sub->ls,l,m,lrg,rrg); if(lrg>m)return hn(cur->rs,sub->rs,m+1,r,lrg,rrg); return hn(cur->ls,sub->ls,l,m,lrg,m)||hn(cur->rs,sub->rs,m+1,r,m+1,rrg); } bool HN(int lt,int rt,int lrg,int rrg) { if(rrg<0)return false; return hn(root[rt],root[lt-1],0,MAXN,max(0,lrg),rrg); } int query(int lt,int rt,int dep,int l,int r,int x,int b) { if(l==r)return l^b; int oi=(b>>dep)&1,m=(l+r)/2; if(oi) { if(HN(lt,rt,l-x,m-x)) return query(lt,rt,dep-1,l,m,x,b); else return query(lt,rt,dep-1,m+1,r,x,b); } else { if(HN(lt,rt,m+1-x,r-x)) return query(lt,rt,dep-1,m+1,r,x,b); else return query(lt,rt,dep-1,l,m,x,b); } } int Query(int b,int x,int l,int r) { return query(l,r,18,0,MAXN,x,b); } int main() { scanf("%d%d",&n,&m); root[0]=bt(0,MAXN); for(int i=1;i<=n;i++) { scanf("%d",&a); root[curt+1]=Change(root[curt],a,0,MAXN); curt++; } for(int i=1;i<=m;i++) { scanf("%d%d%d%d",&b,&x,&l,&r); printf("%d\n",Query(b,x,l,r)); } return 0; } ```