@zzzc18
2017-12-28T20:31:17.000000Z
字数 2156
阅读 1119
bzoj
可持久化数据结构
给定一个初始时为空的整数序列(元素由 开始标号)以及一些询问:
类型1:在数组后面就加入数字 。
类型2:在区间中找到y,最大化()。
类型3:删除数组最后 个元素。
类型4:在区间中,统计小于等于 的元素个数。
类型5:在区间中,找到第 小的数。
因为要求“最大化()”,加上这是个带修改数据结构题,并且还要求别的东西,,这时使用线性基
(我不会)应该用不了01Trie
,可以解决这种问题,并且考虑一番后发现也可以解决类型4、5。
只要将01Trie
可持久化,就可以求出区间的值。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 520000+9;
int tot_len;
struct T{
int ch[2];
int size;
int &operator [] (int x){
return ch[x];
}
}tree[MAXN*20];
int rt[MAXN];
int cnt;
int insert(int pre,int val,int bit_length){
int now=++cnt;
tree[now]=tree[pre];
tree[now].size++;
if(bit_length==-1)
return now;
bool tmp=val&(1<<bit_length);
if(tmp)tree[now][1]=insert(tree[pre][1],val,bit_length-1);
else tree[now][0]=insert(tree[pre][0],val,bit_length-1);
return now;
}
int del(int x){
tot_len-=x;
}
int max_xor(int pre,int now,int val){
int re=0;
for(int bit_length=19;bit_length>-1;bit_length--){
bool tmp=val&(1<<bit_length);
bool jud=tree[tree[now][tmp^1]].size-tree[tree[pre][tmp^1]].size;
if(jud){
re|=(tmp^1)*(1<<bit_length);
pre=tree[pre][tmp^1];now=tree[now][tmp^1];
}
else{
re|=(tmp)*(1<<bit_length);
pre=tree[pre][tmp];now=tree[now][tmp];
}
}
return re;
}
int smallers(int pre,int now,int val){
int re=0;
for(int bit_length=19;bit_length>-1;bit_length--){
bool tmp=val&(1<<bit_length);
if(tmp){
re+=tree[tree[now][0]].size-tree[tree[pre][0]].size;
}
pre=tree[pre][tmp];now=tree[now][tmp];
}
//叶子节点
re+=tree[now].size-tree[pre].size;
return re;
}
int k_th(int pre,int now,int val){
int re=0;
for(int bit_length=19;bit_length>-1;bit_length--){
int tmp=tree[tree[now][0]].size-tree[tree[pre][0]].size;
if(val<=tmp){
pre=tree[pre][0];now=tree[now][0];
}
else{
val-=tmp;
re|=(1<<bit_length);
pre=tree[pre][1];now=tree[now][1];
}
}
return re;
}
int main(){
int kase;
scanf("%d",&kase);
while(kase--){
int opt,x,l,r;
scanf("%d",&opt);
switch(opt){
case 1:scanf("%d",&x);tot_len++;rt[tot_len]=insert(rt[tot_len-1],x,19);break;
case 2:scanf("%d%d%d",&l,&r,&x);printf("%d\n",max_xor(rt[l-1],rt[r],x));break;
case 3:scanf("%d",&x);del(x);break;
case 4:scanf("%d%d%d",&l,&r,&x);printf("%d\n",smallers(rt[l-1],rt[r],x));break;
default:scanf("%d%d%d",&l,&r,&x);printf("%d\n",k_th(rt[l-1],rt[r],x));break;
}
}
return 0;
}