可持久化字典树—例题

题目

来源：loj6144. 「2017 山东三轮集训 Day6」C

给出一个序列，有如下四种操作：
Xor x：给全部数异或x
And x全部数与上x
Or x
Ask l r k求l~r中的第k小

题目就是想要写一个“可持久化线段树和可持久化字典树”。

其实并不好写。

最后观察性质。对于“&”而言，如果与0，那么这位就全部人统一了。与1没有影响。
“|”类似，“^”也类似。

不过每次这种统一操作之后，字典树的样子就不是我们想要的了。所以需要进行一些改造。我想的还是太复杂了，想着只把更改的部分改了，其他地方保持不动。而别人写的是直接重新建树。

这个地方告诉我，一定要好好的分析时间复杂度。时间复杂度算准了，那么就可以重新建树。毕竟重新建树这样的操作是我们反复写过的。而部分修改是需要重新细节构建的。复杂度允许肯定是重新构树要好。

一开始想题的方向是说会不会&、|、^运算有什么我不熟悉的定律，后来发现没有。

总之这题就是一道暴力的题目。关键是细节要处理好。

可持久化字典树

这个算法的思想还是很简单的。不过我还是有一些细节处理不够好。下面总结一些套路，以便以后实现可持久化字典树的时候，不会被这么多细节所烦恼。

首先啊，建造可持久化数据结构，需要有很多个root，每个root表示的是新“链”。

root[id]表示的内容其实是空的，所以一条长为len的字符串(做个假设)，会产生len+1个节点。build的时候从root[id]开始，然后根据s[i]决定走那一个儿子。所以for循环到i的时候，是在处理节点i-1的。就是说i=1时在处理root[id]，……i=n时，在处理s[i-1]的情况。所以一定要注意到，最后s[i]的情况是需要单独在build的地下处理的。千万别忘了！！！

query的时候依旧是这样的一个思想，所以呢第一个点访问的点(也就是root[id])没有任何的信息，只是做了一个开头的工作。而最后一个节点很大概率上是不会真正访问的，因为到那里的时候情况就已经完全确定下来了。(比如说这一题，就是已经确定下来这个数是多少了，所以不访问也是OK的。)所以在访问第i个节点时，我们已经处理的内容的内容是i-1这么的，然后现在要处理的是接下来要去哪个地方，往那个地方去会有什么收益。(这样子收益计算次数就是len次，是对的。)

代码

#include
using namespace std;
const int N=5e4+10;
const int MAXLAY=31;//!!!!!!31

int n,m,a[N][35];
int flg[35];/*flg[i]=-2表示需要一次的反转*/ 
int tot,son[N*35][2],val[N*35];
int root[N];

void insert(int id)
{
	int x=root[id]=++tot,xx=root[id-1];
	for(int i=MAXLAY;i>=1;i--)
	{
		int y=a[id][i];
		if(flg[i]>=0) y=0;
		son[x][y]=++tot;
		son[x][1^y]=son[xx][1^y];
		val[x]=val[xx]+1;
		x=son[x][y];
		xx=son[xx][y];//debug xx=son[x][y];
	}
	val[x]=val[xx]+1;
}

void build()
{
	tot=1;
	memset(son,0,sizeof(son));
	memset(val,0,sizeof(val));
	for(int i=1;i<=n;i++)
	{
		insert(i);
	}
}

int query(int l,int r,int K)
{
	K--;							//debug K should --
	int ret=0;
	l=root[l];r=root[r];
	for(int i=MAXLAY;i>=1;i--)
	{
		if(flg[i]>=0)
		{
			l=son[l][0];
			r=son[r][0];
			if(flg[i]==1) ret+=1<<(i-1);
		}
		else
		{
			int fan=flg[i]==-2?1:0;
			if(K>=val[ son[r][fan^0] ] - val[ son[l][fan^0] ])		//debug //debug K>=val[]-val[]
			{
				K-=val[ son[r][fan^0] ] - val[ son[l][fan^0] ];
				l=son[l][fan^1];
				r=son[r][fan^1];
				ret+=1<<(i-1);
			}
			else
			{
				l=son[l][fan^0];
				r=son[r][fan^0];
			}
		}
	}
	return ret;
}


void getnum(int id,int x)			//debug %10??
{
	for(int i=1;i<=31;i++)
	{
		a[id][i]=x&1;
		x>>=1;
	}
}

char opt[10];
int main()
{
	scanf("%d%d",&n,&m);
	int orsum=0,andsum=(1ll<<30)-1;
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		orsum|=x;
		andsum&=x;
		getnum(i,x);
//		build(i);					//build before flg
	}
//	getnum(0,orsum);
//	getnum(1,andsum);		debug getnum after getnum(1)
	for(int i=1;i<=MAXLAY;i++)
	{
		if((andsum&1) == (orsum&1)) flg[i]=a[0][i];
		else flg[i]=-1;
		andsum>>=1;
		orsum>>=1;
	}
	build();
	while(m--)
	{
		scanf("%s",opt);
		if(opt[0]=='X')//Xor
		{
			int x;
			scanf("%d",&x);
			getnum(0,x);
			for(int i=MAXLAY;i>=1;i--)
			{
				if(a[0][i]==1 && flg[i]>=0) flg[i]^=1;
				else if(a[0][i]==1) flg[i]=-3-flg[i];
			}
		}
		else if(opt[0]=='O')//Or
		{
			int x;
			scanf("%d",&x);
			getnum(0,x);
			bool need=false;
			for(int i=MAXLAY;i>=1;i--)
			{
				if(a[0][i]==1 && flg[i]<=-1)
				{
					flg[i]=1;
					need=true;
				}
				else if(a[0][i]==1 && flg[i]==0)
				{
					flg[i]=1;
				}
			}
			if(need) build();
		}
		else if(opt[1]=='n')//And
		{
			int x;
			scanf("%d",&x);
			getnum(0,x);
			bool need=false;
			for(int i=MAXLAY;i>=1;i--)
			{
				if(a[0][i]==0 && flg[i]<=-1)		//debug flg[i]==-1
				{
					flg[i]=0;
					need=true;
				}
				else if(a[0][i]==0 && flg[i]==1)
				{
					flg[i]=0;
				}
			}
			if(need) build();
		}
		else//Ask
		{
			int l,r,K;
			scanf("%d%d%d",&l,&r,&K);
			int ans=query(l-1,r,K);
			printf("%d\n",ans);
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168