[2019寒假集训day3]欧铂瑞特(主席树/trie树)

题面

题解

比较巧妙的一道卡空间题。
首先注意到题目有查询$k$小，还支持在末尾添加和删除，就可以反应出来这是一道主席树的题目。
但是，我们并不能够支持最大异或操作。
我们知道最大异或是可以从二进制高位开始贪心得到的。
考虑一颗叶子结点为2k2^k2k个的线段树。
显然，它是一颗完全二叉树。
可以发现的是:对于每个第$i$层(从0开始计数)的非叶节点，那么它的的儿子分别代表从高位至低位的第$i+1$位是$0$还是$1$。
可以将其理解为一个线段树版的trie树。
这样就可以愉快的贪心了~。
时间复杂度:$O(n\log n)$

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
#define MAXN 500000
int Q,n,rt[MAXN+5];
int read()
{int f=1,x=0;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x;
}
struct Seg_tree
{int ch[MAXN*20+5][2],sum[MAXN*20+5],pcnt;Seg_tree(){pcnt=0;}void Insert(int &x1,int x2,int mask,int val){x1=++pcnt;sum[x1]=sum[x2]+1;if(mask==0)return ;if(!(val&mask)){ch[x1][1]=ch[x2][1];Insert(ch[x1][0],ch[x2][0],mask>>1,val);}else {ch[x1][0]=ch[x2][0];Insert(ch[x1][1],ch[x2][1],mask>>1,val);}}int Query1(int x1,int x2,int mask,int val){if(mask==0)return 0;if(mask&val){if(sum[ch[x2][0]]-sum[ch[x1][0]]>0)return Query1(ch[x1][0],ch[x2][0],mask>>1,val)+mask;else return Query1(ch[x1][1],ch[x2][1],mask>>1,val);}else{if(sum[ch[x2][1]]-sum[ch[x1][1]]>0)return Query1(ch[x1][1],ch[x2][1],mask>>1,val)+mask;else return Query1(ch[x1][0],ch[x2][0],mask>>1,val);}}int Query2(int x1,int x2,int mask,int val){if(mask==0)return sum[x2]-sum[x1];if(mask&val)return sum[ch[x2][0]]-sum[ch[x1][0]]+Query2(ch[x1][1],ch[x2][1],mask>>1,val);else return Query2(ch[x1][0],ch[x2][0],mask>>1,val);}int Query3(int x1,int x2,int mask,int cnt){if(mask==0)return 0;int tmp=sum[ch[x2][0]]-sum[ch[x1][0]];if(tmp>=cnt)return Query3(ch[x1][0],ch[x2][0],mask>>1,cnt);else return Query3(ch[x1][1],ch[x2][1],mask>>1,cnt-tmp)+mask;}
}T;
int main()
{//freopen("operator.in","r",stdin);//freopen("operator.out","w",stdout); scanf("%d",&Q);int op,st=1<<18,l,r,x;while(Q--){op=read();if(op==0){n++;T.Insert(rt[n],rt[n-1],st,read());continue;}if(op==2){n-=read();continue;}l=read(),r=read();if(op==1){x=read();printf("%d\n",x^T.Query1(rt[l-1],rt[r],st,x));}if(op==3)printf("%d\n",T.Query2(rt[l-1],rt[r],st,read()));if(op==4)printf("%d\n",T.Query3(rt[l-1],rt[r],st,read()));}
}