首页 > 代码库 > Codeforces 706D Vasiliy's Multiset（可持久化字典树）
Codeforces 706D Vasiliy's Multiset（可持久化字典树）
【题目链接】 http://codeforces.com/problemset/problem/706/D
【题目大意】
要求实现一个集合中的三个操作，1：在集合中加入一个元素x，2：从集合中删除一个元素x（保证x存在），3：要求从集合中选出一个数，使得其与给出的数x的异或值最大，输出这个异或值。
【题解】
可以将所有的以二进制形式存在01字典树上，删除即插入权值为-1的二进制串，对于异或值最大的操作，我们只要在字典树上按位贪心，从最高位开始尽量保证该位存在最后就能得到答案。写代码的时候直接写了个持久化的字典树，普通字典树也可以实现这样子的功能。
【代码】
#include <cstdio>#include <algorithm> const int N=600005,inf=2000000000;using namespace std;int bin[32],n,m,a[N],b[N],root[N];struct trie{ int cnt,ch[N*32][2],sum[N*32]; int insert(int x,int val,int d){ int tmp,y;tmp=y=++cnt; for(int i=30;i>=0;i--){ int t=val&bin[i];t>>=i; ch[y][0]=ch[x][0];ch[y][1]=ch[x][1]; x=ch[x][t]; y=ch[y][t]=++cnt; sum[y]=sum[x]+d; }return tmp; } int query(int l,int r,int val){ int tmp=0; for(int i=30;i>=0;i--){ int t=val&bin[i];t>>=i; if(sum[ch[r][t^1]]-sum[ch[l][t^1]])tmp+=bin[i],r=ch[r][t^1],l=ch[l][t^1]; else r=ch[r][t],l=ch[l][t]; }return tmp; }}T;int Q,x;char t;int main(){ bin[0]=1;for(int i=1;i<=30;i++)bin[i]=bin[i-1]<<1; scanf("%d",&Q); root[1]=T.insert(root[0],0,1); for(int i=2;i<=Q+1;i++){ scanf(" %c %d",&t,&x); if(t==‘+‘)root[i]=T.insert(root[i-1],x,1); else if(t==‘-‘)root[i]=T.insert(root[i-1],x,-1); else printf("%d\n",T.query(root[0],root[i]=root[i-1],x)); }return 0;}
Codeforces 706D Vasiliy's Multiset（可持久化字典树）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。