【模板】可持久化Trie树

理解了所谓⌈可持久化⌋的含义之后也就没多难了。

\(\textrm{luogu P4735 最大异或和}\)

#include <iostream>
const int N = 3e5+10;
struct TRIE {
	int sid[2];
	int cnt;
} trie[N*64];
int trie_tot;
#define cnt(id) trie[id].cnt
#define sid(id,ch) trie[id].sid[ch]
int insert(int id,int x,int depth) {
	int new_node = ++trie_tot;
	cnt(new_node) = cnt(id)+1;
	if(depth == 0) 
		return new_node;
	sid(new_node,(x>>(depth-1))&1) = insert(sid(id,(x>>(depth-1))&1),x,depth-1);
	sid(new_node,!((x>>(depth-1))&1)) = sid(id,!((x>>(depth-1))&1));
	return new_node;
}
int query(int pst,int ftr,int val,int depth) {
	if(depth <= 0) 
		return 0;
	if(cnt(sid(ftr,!((val>>(depth-1))&1)))-cnt(sid(pst,!((val>>(depth-1))&1))) > 0) 
		return (1<<(depth-1))+query(sid(pst,!((val>>(depth-1))&1)),sid(ftr,!((val>>(depth-1))&1)),val,depth-1);
	else 
		return query(sid(pst,(val>>(depth-1))&1),sid(ftr,(val>>(depth-1))&1),val,depth-1);
}
void dfs(int id,int depth) {
	if(depth < 0) 
		return;
	printf("%d(%d %d) : %d : %d\n",id,sid(id,0),sid(id,1),depth,cnt(id));
	if(sid(id,0))
		dfs(sid(id,0),depth-1);
	if(sid(id,1))
		dfs(sid(id,1),depth-1);
	printf("%d complete\n",id);
}
int n, m;
int a[N];
int root[N<<1];
int ver_tot;
int now_xor;
int l, r, x;
char opt[2];
int main() {
	scanf("%d %d",&n,&m);
	for(register int i = 1;i <= n;++i) 
		scanf("%d",&a[i]);
	for(register int i = n;i >= 1;--i) 
		a[i] ^= a[i+1];
	for(register int i = 1;i <= n;++i) 
		root[i] = insert(root[i-1],a[i],24);
	ver_tot = n;
	for(register int i = 1;i <= m;++i) {
		scanf("%s",opt);
		switch(opt[0]) {
			case 'A' :
				scanf("%d",&x);
				now_xor ^= x;
				++ver_tot;
				root[ver_tot] = insert(root[ver_tot-1],x^now_xor,24);
				break;
			case 'Q' :
				scanf("%d %d %d",&l,&r,&x);
				printf("%d\n",query(root[l-1],root[r],x^now_xor,24));
				break;
			case 'D' : 
				scanf("%d",&x);
				dfs(root[x],24);
		}
	}
	return 0;
}