记录编号	560761	评测结果	AAAAAAAAAA
题目名称	[BZOJ 3261]最大区间异或和	最终得分	100
用户昵称	huaruoji	是否通过	通过
代码语言	C++	运行时间	1.670 s
提交时间	2021-05-10 20:39:39	内存使用	204.14 MiB

#include <bits/stdc++.h>
#define endl '\n'
typedef long long ll;

using namespace std;
const int N = 6e5 + 1;
int n, m, p, s[N];

inline int getbit(int x, int k) {
	return (x >> k) & 1;
}

namespace trie {
	int nodeCnt, rt[N];
	struct node {
		int cnt, latest;
		int ch[2];
	}c[N * 27];
	void make(const int s, int now, int fa) {
		c[++nodeCnt] = c[rt[fa]];
		rt[now] = nodeCnt;
		now = nodeCnt;
		for(int i = 24; i >= 0; i--) {
			int v = getbit(s, i);
			if(!c[now].ch[v]) c[now].ch[v] = ++nodeCnt;
			else {
				c[++nodeCnt] = c[c[now].ch[v]];
				c[now].ch[v] = nodeCnt;
			}
			++c[nodeCnt].cnt;
			c[nodeCnt].latest = p;
			now = nodeCnt;
		}
	}
	int query(int u, int l, int val) {
		if(u == 0) return val;
		int ans = 0;
		for(int i = 24; i >= 0; i--) {
			int v = getbit(val, i);
			if(c[u].ch[v ^ 1] && c[c[u].ch[v ^ 1]].latest >= l) 
				u = c[u].ch[v ^ 1], ans += 1 << i;
			else u = c[u].ch[v];
		}
		return ans;
	}
}

int main() {
	freopen("xorsum.in", "r", stdin);
	freopen("xorsum.out", "w", stdout);
	
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m;
	char op; int l, r, x;
	for(int i = 1; i <= n; i++) {	
		cin >> x;
		s[i] = s[i - 1] ^ x;
		trie::make(s[i], ++p, i - 1);
	}
	for(int i = 1; i <= m; i++) {
		cin >> op;
		if(op == 'A') {
			cin >> x;
			++p;
			s[p] = s[p - 1] ^ x;
			trie::make(s[p], p, p - 1);
		} else {
			cin >> l >> r >> x;
			cout << trie::query(trie::rt[r - 1], l - 1, x ^ s[p]) << endl;
		}
	}
	
	return 0;
}