「Test」腿部挂件

题意：多次询问，每次询问给出三个数 $x,l,r$，即求 $x$ 与数列 $a _i$ 中 $[l,r]$ 的区间中一个数所得到的异或最大值。

很明显，多个数中异或最大值，字典树即可解决。

但是加上区间这个条件，自然而然想到可持久化。

可持久化字典树的建树方式和可持久化线段树区别不大，都是不用完全重开一个新的字典树来保存历史版本，直接从上一个历史版本更新即可。即需要改变的才新开节点，不需要的直接用上一个历史版本的即可。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<ctime>
#define INF 1e9
using namespace std;
const int maxn=200010;
const double Pi=acos(-1.0);
template<class T>void read(T &x)
{
	x=0;int f=0;char ch=getchar();
	while(ch<'0'||ch>'9') {f|=(ch=='-');ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	x=f?-x:x;
	return;
}
int n,q,a[maxn],trie[maxn*30][2];
int root[maxn],tot;
int insert(int last,int x)
{
	int p,q;
	p=q=++tot;
	for(int i=30;i>=0;i--)
	{
		int k=(x>>i)&1;
		trie[p][k^1]=trie[last][k^1];
		if(!trie[p][k])
			trie[p][k]=++tot;
		p=trie[p][k];
		last=trie[last][k];
	}
	return q;
}
int query(int l,int r,int x)
{
	int ans=0;
	for(int i=30;i>=0;i--)
	{
		int k=(x>>i)&1;
		k^=1;
		if(trie[l][k]^trie[r][k])
		{
			ans|=(1<<i);
			l=trie[l][k];
			r=trie[r][k];
		}
		else
		{
			l=trie[l][k^1];
			r=trie[r][k^1];
		}
	}
	return ans;
}
int main()
{
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		root[i]=insert(root[i-1],a[i]);
	}
	for(int i=1;i<=q;i++)
	{
		int x,l,r;
		scanf("%d%d%d",&x,&l,&r);
		printf("%d\n",query(root[l],root[r+1],x));
	}
	return 0;
}