某天%你赛出现了一个题目。
我瞎几把做了一下发现需要支持一个区间异或和全局查 \(\geq k\) 的数量的数据结构。
赛后想起来好像不可做。
但是我考场没有智慧，发现不能线段树。然后想到分块，就变成了几个整块全局异或和散块暴力重构。
于是考场搓了个踹。自己随便测了一下好像是对的/yiw
时间复杂度是高贵的 \(O(n\sqrt{n}\log(n))\) ！！！11
可以和正解差不多难写的情况下拿下 \(50\) pts 的高分，我太牛啦！！！！！11
struct Trie {
int rt[1200005], flip[1200005][35], cnt[300005 * 35];
int t[300005 * 35][2], siz[3000005];
int tot;
inline Trie() { tot = 0; }
inline void insert(int id, uint x) {
if(!rt[id]) rt[id] = ++tot;
int u = rt[id];
siz[u] += 1;
for(int i = 31; i >= 0; i--) {
if((flip[id][i] & 1) != (cnt[u] & 1)) swap(t[u][1], t[u][0]), cnt[u]++;
if(!t[u][(x >> i) & 1]) t[u][(x >> i) & 1] = ++tot;
u = t[u][(x >> i) & 1];
siz[u] += 1;
}
}
inline int query(int id, uint k, int ret = 0) {
if(!rt[id]) rt[id] = ++tot;
int u = rt[id];
for(int i = 31; i >= 0; i--) {
if((flip[id][i] & 1) != (cnt[u] & 1)) swap(t[u][1], t[u][0]), cnt[u]++;
if(!t[u][(k >> i) & 1]) t[u][(k >> i) & 1] = ++tot;
if(!((k >> i) & 1)) u = t[u][(k >> i) & 1];
else {
ret += siz[t[u][0]];
u = t[u][1];
}
}
return siz[rt[id]] - ret;
}
inline void XOR(int id, uint x) {
if(!rt[id]) rt[id] = ++tot;
for(int i = 0; i <= 31; i++) flip[id][i] += ((x >> i) & 1);
}
} trie;