关于可持久化Trie

我认为可持久化Trie 主要指可持久化01Trie

如洛谷P4735

将每个数的异或前缀和转化为二进制，添加前缀0至相同位数，然后从最高位开始插入，类似主席树，每一层都对需要更新的点加入一个新的点，同时统计所有在\(i\)之前的数该位为\(1/0\)的总个数（即siz）。

每次查询，从根节点开始，贪心地选与这一位相反的值，同时用第\(r\)个版本减去第\(l-1\)个版本（类似主席树）。

代码：

#include<bits/stdc++.h>

using namespace std;

inline int read()

{

	char ch=getchar();

	while(!isdigit(ch)) ch=getchar();

	int ans=0;

	while(isdigit(ch))

	{

		ans=ans*10+ch-48;

		ch=getchar();

	}

	return ans;

}

#define N 300005

struct Trie

{

	struct Node

	{

		int ch[2];

		int siz;

	};

	Node t[N*48];

	int ncnt;

	int rcnt,rot[N*2];

	void insert(int x,int rt)

	{

		rt=rot[rt];

		int cur=rot[++rcnt]=++ncnt;

		for(int i=24;i>=0;i--)

		{

			int tmp=(x>>i)&1;

			t[cur].ch[tmp]=++ncnt;

			t[cur].ch[tmp^1]=t[rt].ch[tmp^1];

			t[cur].siz=t[rt].siz+1;

			cur=t[cur].ch[tmp];

			rt=t[rt].ch[tmp];

		}

		t[cur].siz=t[rt].siz+1;

	}

	int query(int x,int l,int r)

	{

//		printf("%d %d %d\n",x,l,r);

		int ans=0;

		int rtl=rot[l-1];

		int rtr=rot[r];

		for(int i=24;i>=0;i--)

		{

			int tmp=(x>>i)&1;

			if(t[t[rtr].ch[tmp^1]].siz-t[t[rtl].ch[tmp^1]].siz>0)

			{

//				printf("** %d",i);

				ans^=(1<<i);

				rtr=t[rtr].ch[tmp^1];

				rtl=t[rtl].ch[tmp^1];

			}

			else

			{

				rtr=t[rtr].ch[tmp];

				rtl=t[rtl].ch[tmp];

			}

		}

		return ans;

	}

};

Trie tr;

int main()

{

	int n,m;

	cin>>n>>m;

	int x=0;

	tr.insert(0,0);

	for(int i=1;i<=n;i++)

	{

		x^=read();

		tr.insert(x,i);

	}

	char opt[3];

	for(int i=1;i<=m;i++)

	{

		scanf("%s",&opt);

		if(opt[0]=='A')

		{

			x^=read();

			tr.insert(x,tr.rcnt);

		}

		else

		{

			int l,r,xx;

			l=read(),r=read(),xx=read();

			printf("%d\n",tr.query(xx^x,l,r));

		}

	}

	return 0;

}

巴特西

关于可持久化Trie

我认为可持久化Trie 主要指可持久化01Trie

最新文章

热门文章

巴特西

关于可持久化Trie

我认为 可持久化Trie 主要指 可持久化01Trie

最新文章

热门文章

我认为可持久化Trie 主要指可持久化01Trie