tql @[又又大柚纸](/space/show?uid=50131)
by salix_leaf @ 2019-03-07 21:13:50
您最新的提交好像只是TLE了诶
by salix_leaf @ 2019-03-07 21:22:37
qaq大佬，据我的观察有些地方可以卡常
```cpp
int k = val & bin[i];
k >>= i;
```
应该可以改成
```cpp
int k = (val>>i)&1;
```
by salix_leaf @ 2019-03-07 21:26:49
然后
```cpp
tmp += bin[i]
```
可以改
```cpp
tmp+=(1<<i)
```
by salix_leaf @ 2019-03-07 21:32:16
其实我觉得可能最耗时间的是cin>>op
我改用了getchar()
开O2A了
您的代码
```cpp
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
inline int read() {
int x = 0; char c = getchar();
while (!isdigit(c)) c = getchar();
while (isdigit(c)) x = x*10 + c-'0', c = getchar();
return x;
}
const int N = 6e5 + 10;
int n, m, a[N], b[N];
int cnt, root[N], sum[N<<5], ch[N<<5][2];
int ins(int x, int val) {
int y, tmp;
y = tmp = ++cnt;
for (int i = 23; i >= 0; --i) {
ch[y][0] = ch[x][0];
ch[y][1] = ch[x][1];
sum[y] = sum[x] + 1;
int k = (val>>i)&1;
x = ch[x][k];
ch[y][k] = ++cnt;
y = ch[y][k];
}
sum[y] = sum[x] + 1;
return tmp;
}
int query(int l, int r, int val) {
int tmp = 0;
for (int i = 23; i >= 0; --i) {
int k = (val>>i)&1;
if (sum[ch[r][k^1]] > sum[ch[l][k^1]])
tmp += 1<<i, r = ch[r][k^1], l = ch[l][k^1];
else
r = ch[r][k], l = ch[l][k];
}
return tmp;
}
int main() {
cin >> n >> m;
n++;
for (int i = 2; i <= n; ++i) a[i] = read();
for (int i = 1; i <= n; ++i) b[i] = b[i-1] ^ a[i];
for (int i = 1; i <= n; ++i)
root[i] = ins(root[i-1], b[i]);
for (int i = 1; i <= m; ++i) {
char op=getchar();
while(op!='A'&&op!='Q') op=getchar();
if (op == 'A') {
n++;
a[n] = read();
b[n] = b[n-1] ^ a[n];
root[n] = ins(root[n-1], b[n]);
} else {
int l, r, x;
l = read(), r = read(), x = read();
printf("%d\n", query(root[l-1], root[r], x^b[n]));
}
}
return 0;
}
```
by salix_leaf @ 2019-03-07 21:33:53
@[又又大柚纸](/space/show?uid=50131) 感觉好巧啊
by salix_leaf @ 2019-03-07 21:37:52
@[salix_leaf](/space/show?uid=59700) Orz
by GaoZiyou @ 2019-03-07 22:00:26
@[salix_leaf](/space/show?uid=59700) 谢谢大佬
by GaoZiyou @ 2019-03-07 22:00:48
@[又又大柚纸](/space/show?uid=50131)
您才是大佬，我太菜了
by salix_leaf @ 2019-03-08 19:49:33
初学OI做可持久化trie？
by ferrum_cccp @ 2019-04-03 21:24:18