Description：

给定一个非负整数序列 $\{a\}$ ，初始长度为 $N$ 。有M个操作，有以下两种操作类型：

1. $A$ $x$ ：添加操作，表示在序列末尾添加一个数 $x$ ，序列的长度 $N+1$ 。 2. $Q$ $l$ $r$ $x$ ：询问操作，你需要找到一个位置 $p$ ，满足 $l \le p \le r$ ，使得： $a[p]\ xor\ a[p+1]\ xor\ \dots \ xor\ a[N]\ xor\ x$ 最大，输出最大是多少。

$N,M\le300000 $

Solution：

设 $sum[i]$ 为异或前缀和，则要求的就是使得 $x\ xor\ sum[p-1] \ xor\ sum[n]$ 最大的 $p$ ，可以对 $sum[i]$ 建立可持久化 $trie$ ，像主席树那样，每次新建从根到叶子的一条链即可。然后两个可持久化 $trie$ 树相减即可得到区间的 $trie$ 树，然后贪心即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 300010

inline char getc()

{

	register char c = getchar();

	while(c != 'A' && c != 'Q')c = getchar();

	return c;

}

inline int read()

{

	register int res = 0;

	register char c = getchar();

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

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int sum[MAXN << 1];

int a[MAXN << 1];

struct node

{

	int c[2];

	int cnt;

	node(){cnt = 0;}

}t[MAXN * 70];

int ptr = 0;

int newnode(){return ++ptr;}

int root[MAXN << 1];

void init()

{

	root[1] = newnode();

	int cur = root[1];

	t[cur].cnt = 1;

	for(int i = 0;i <= 25;++i)

	{

		t[cur].c[0] = newnode();

		cur = t[cur].c[0];

		t[cur].cnt = 1;

	}

	return;

}

void insert(int &rt,int val,int cur)

{

	int p = newnode();t[p] = t[rt];rt = p;

	if(cur == -1){t[rt].cnt += 1;return;}

	insert(t[rt].c[(val >> cur) & 1],val,cur - 1);

	t[rt].cnt = t[t[rt].c[0]].cnt + t[t[rt].c[1]].cnt;

	return;

}

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

{

	if(cur == -1)return 0;

	int w = (((x >> cur) & 1) ^ 1);

	if(t[t[r].c[w]].cnt - t[t[l].c[w]].cnt > 0)

		return ((1 << cur) | query(t[r].c[w],t[l].c[w],x,cur - 1));

	else return query(t[r].c[w ^ 1],t[l].c[w ^ 1],x,cur - 1);

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)a[i] = read();

	init();

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

	{

		sum[i] = sum[i - 1] ^ a[i];

		root[i + 1] = root[i];

		insert(root[i + 1],sum[i],25);

	}

	char c;

	int l,r,x;

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

	{

		c = getc();

		if(c == 'A')

		{

			++n;

			a[n] = read();

			sum[n] = sum[n - 1] ^ a[n];

			root[n + 1] = root[n];

			insert(root[n + 1],sum[n],25);

		}

		else

		{

			l = read();r = read();x = read();

			printf("%d\n",query(root[r],root[l - 1],(sum[n] ^ x),25));

		}

	}

	return 0;

}