调了半天发现数组开小了,维护前缀和第二维下标写错了。
看到异或容易想到 Trie 树。
那么考虑每一个操作如何进行。
第一个操作直接 Trie 上插入就好了。
第二个操作发现是区间求和。那么想到维护一个前缀和,对于 Trie 的更新也随之更新即可。
第三个操作是全局异或,直接记一个 \(xor\) 表示当前异或标记即可,插入的时候直接异或这个标记再插入就好了。
第四个操作是排序。
很容易想到排序会打乱前面三个操作的顺序。但是想一下,这个 Trie 本身 \(0\)/\(1\) 就代表了数的大小关系,即对于已经插入的部分显然已经有序。那么前面所有操作可以转化为对于一个序列,前半部分有序,后半部分无序,求区间和。
但是操作三会改变原来维护的前缀和啊?没关系,对于一个 \(xor\) 标记,如果当前位为 \(1\) 那么交换两个子树;否则形态不变。
二操作拆成两段前缀和就很好维护了。
一操作也就不需要进行插入操作了,只需要维护以下后面无序部分的前缀和就可以了。
在这个意义上进行维护即可。
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
template <typename T> inline void read(T &x) {
x = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar());
for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
return ;
}
const int N = 2e5 + 10, MAX = 31;
int n, m, Xor, tot = 1, ordered_n, a[N], tag[MAX];
int siz[N << 4], ch[N << 4][2], sum_u[N][MAX], sum_o[N << 4][MAX];
inline void ins(int x) {
int cur = 1; ++siz[cur];
for (int bit = 0; bit < MAX; ++bit) sum_o[cur][bit] += (x >> bit & 1);
for (int i = MAX - 1; ~i; --i, ++siz[cur]) {
int to = x >> i & 1;
if (!ch[cur][to]) ch[cur][to] = ++tot; cur = ch[cur][to];
for (int bit = 0; bit < MAX; ++bit) sum_o[cur][bit] += (x >> bit & 1);
}
return ;
}
inline ll query_o(int x) {
int cur = 1; ll res = 0; int ex = 0;
for (int i = MAX - 1; ~i; --i) {
if (x <= siz[ch[cur][tag[i]]])
cur = ch[cur][tag[i]], ex |= (tag[i] << i);
else {
x -= siz[ch[cur][tag[i]]]; int to = tag[i] ^ 1;
for (int bit = 0; bit < MAX; ++bit) {
int curans = sum_o[ch[cur][tag[i]]][bit];
if (Xor >> bit & 1) curans = siz[ch[cur][tag[i]]] - curans;
res += (ll)curans << bit;
}
cur = ch[cur][to], ex |= (to << i);
}
}
return res + (ll)(Xor ^ ex) * x;
}
inline ll query_u(int l, int r) {
ll res = 0;
for (int i = 0; i < MAX; ++i) {
int curans = sum_u[r][i] - sum_u[l - 1][i];
if (Xor >> i & 1) curans = r - l + 1 - curans;
res += (ll)curans * (1 << i);
}
return res;
}
inline ll query(int l, int r) {
if (r <= ordered_n) return query_o(r) - query_o(l - 1);
if (ordered_n < l) return query_u(l, r);
return query_o(ordered_n) - query_o(l - 1) + query_u(ordered_n + 1, r);
}
inline void solve() {
int opt, l, r, x; read(opt);
if (opt == 1) {
read(a[++n]), a[n] ^= Xor;
for (int bit = 0; bit < MAX; ++bit)
sum_u[n][bit] = sum_u[n - 1][bit] + (a[n] >> bit & 1);
} else if (opt == 2) {
read(l), read(r); printf("%lld\n", query(l, r));
} else if (opt == 3) {
read(x), Xor ^= x;
} else {
for (int i = ordered_n + 1; i <= n; ++i) ins(a[i]);
for (int bit = 0; bit < MAX; ++bit) tag[bit] = Xor >> bit & 1;
ordered_n = n; for (int bit = 0; bit < MAX; ++bit) sum_u[n][bit] = 0;
}
return ;
}
int main() {
read(n);
for (int i = 1; i <= n; ++i) {
read(a[i]);
for (int bit = 0; bit < MAX; ++bit)
sum_u[i][bit] = sum_u[i - 1][bit] + (a[i] >> bit & 1);
}
read(m);
while (m--) solve();
return 0;
}
标签:ch,cur,int,MAX,实验班,Sol,read,P5312,bit
From: https://www.cnblogs.com/MistZero/p/P5312-Sol.html