题解 P5312 【[Ynoi2011]D2T1】
诗乃
2019-10-25 21:35:21
首先不难发现在某一个时刻数列一定是前一段有序后一段无序。
3操作是全局异或，直接开个全局变量记录异或值即可。对于后来新加入的数，先异或上这个全局变量再插入即可。
考虑无排序操作时，即无序段的处理，不难想到拆位，维护每一位上1的出现次数的前缀和。设查询位置为$p$，全局异或值为$X$，该位前缀和为$prf_{p}$，则若$X$的这一位为1则区间内该位为1的数字个数为$p-prf_p$，否则为$prf_p$。分开计算每一位对答案的贡献即可实现区间求和。
考虑无插入操作时，即有序段的处理，不难想到维护$01Trie$树，与线段树类似，Trie树每一层的节点将当前区间分成该位为0和该位为1两段区间。用类似线段树的标记处理，每个节点上分别维护所有位的出现次数之和，查询时类似线段树查询即可查询位前缀和。
当执行4操作时，之前的3操作会改变前面$01Trie$上的数字顺序。不难发现，某一位异或1即把这一位对应$Trie$树的那一层所有左右节点交换。
把前面两种做法综合起来，排序时将无序段的数插入$01Trie$中，随后维护$3$操作带来的影响。切了。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 50, MW = 30;
typedef long long lint;
int read() {
char ch; int x; while(ch = getchar(), ch < '!'); x = ch - 48;
while(ch = getchar(), ch > '!') x = (x << 3) + (x << 1) + ch - 48; return x;
}
int ch[MAXN << 4][2], X, pre[MAXN][MW+5], s[MAXN << 4][MW+5], cntc = 1, n, _n, tag[MW+5], a[MAXN], m, siz[MAXN << 4];
lint qry(int p) {
if(p == 0) return 0;
lint res = 0; int val = 0, u = 1;
for(int i = MW; i >= 0; --i) {
if(p <= siz[ch[u][tag[i]]]) u = ch[u][tag[i]], val |= tag[i] << i;
else {
int x = siz[ch[u][tag[i]]]; p -= x;
for(int j = 0; j <= MW; ++j){
int cnt = s[ch[u][tag[i]]][j];
if(X>>j&1) cnt = x - cnt;
res += (1ll*cnt) << j;
}
u = ch[u][tag[i]^1];
val |= (tag[i]^1) << i;
}
}
return res + 1ll * (val ^ X) * p;
}
void insert(int x) {
int u = 1; for(int i = MW; i >= 0; --i) {
++siz[u];
for(int j = 0; j <= MW; ++j) s[u][j] += ((x>>j)&1);
int p = ((x>>i)&1);
u = ch[u][p] ? ch[u][p] : ch[u][p] = ++cntc;
} ++siz[u];
for(int j = 0; j <= MW; ++j) s[u][j] += x>>j&1;
}
lint qryx(int l, int r) {
int len = r - l + 1; lint res = 0;
for(int i = 0; i <= MW; ++i) {
int cnt = pre[r][i] - pre[l-1][i];
if(X>>i&1) cnt = len - cnt;
res += (1ll*cnt) << i;
} return res;
}
void srt() {for(int i = 0; i <= MW; ++i) tag[i] = (X>>i)&1;}
lint query(int l, int r) {
if(r <= _n) return qry(r) - qry(l-1);
if(l > _n) return qryx(l, r);
return qry(_n) - qry(l-1) + qryx(_n+1, r);
}
int main() {
n = read(); _n = 0;
for(int i = 1; i <= n; ++i) {
a[i] = read();
for(int k = 0; k < MW; ++k)
pre[i][k] = pre[i-1][k] + ((a[i]>>k)&1);
} m = read();
for(int opt, l, r, x; m--; ) {
opt = read();
if(opt == 1) {
a[++n] = read(); a[n] ^= X;
for(int k = 0; k < MW; ++k)
pre[n][k] = pre[n-1][k] + ((a[n]>>k)&1);
}
if(opt == 2) {
l = read(); r = read();
printf("%lld\n", query(l, r));
}
if(opt == 3) x = read(), X ^= x;
if(opt == 4) {
for(int i = _n+1; i <= n; ++i) insert(a[i]);
_n = n; srt();
memset(pre[n], 0, sizeof pre[n]);
}
}
}
```