二次联通门 : LibreOJ #517. 「LibreOJ β Round #2」计算几何瞎暴力
/* LibreOJ #517. 「LibreOJ β Round #2」计算几何瞎暴力 叫做计算几何 实则毒瘤数据结构 看到xor后 考虑Trie树 Trie树的每一个节点保存的是以当前子树中每个二进制位的个数 给Trie打一个全局xor标记，如果标记这一位是1，就交换它的两个儿子 另外维护一个前缀和 前缀和存的是没sort过的值的和 Trie维护的是sort之后的值 1操作直接在前缀和后加就好 2操作在前缀和和Trie树中一起查 */ #include <cstdio> #include <iostream> #define rg register const int BUF = 10000010; char Buf[BUF], *buf = Buf; typedef long long LL; inline void read (int &n) { bool temp = false; for (n = 0; !isdigit (*buf); ++ buf) if (*buf == '-') temp = true; for (; isdigit (*buf); n = n * 10 + *buf - '0', ++ buf); if (temp) n = -n; } #define Max 200009 struct T_D { T_D *c[2]; int s, thb[31]; }; int s[Max][31], v[Max]; int _T, _S, C, T; class Trie { private : T_D poor[Max * 31], *Tail, *Root, *null; private : inline T_D *New () { T_D *now = Tail ++; now->c[0] = now->c[1] = null, now->s = 0; return now; } public : Trie () { Tail = poor, null = Tail ++, null->c[0] = null->c[1] = null; null->s = 0, Root = New (); } void Insert (const int &k) { T_D *n = Root; ++ T; for (rg int i = 30, j; i >= 0; -- i) { if (n->c[(k >> i) & 1] == null) n->c[(k >> i) & 1] = New (); n = n->c[(k >> i) & 1], ++ n->s; for (j = 0; j <= 30; ++ j) n->thb[j] += (k >> j) & 1; } } inline void P (const int &key) { v[++ C] = key; for (rg int i = 0; i <= 30; ++ i) s[C][i] = s[C - 1][i] + ((key >> i) & 1); } inline void ReBuild () { for (; C; Insert (v[C --])); _S = _T; } LL Find (int k) { T_D *n = Root; LL r = 0; rg int i, j; for (i = 30; i >= 0; -- i) { if (k == 0) break; if (k < n->c[(_S >> i) & 1]->s) n = n->c[(_S >> i) & 1]; else { T_D *p = n->c[(_S >> i) & 1]; k -= p->s; for (j = 0; j <= 30; ++ j) if ((_T >> j) & 1) r += (LL) (p->s - p->thb[j]) << j; else r += (LL) p->thb[j] << j; n = n->c[(_S >> i) & 1 ^ 1]; } } for (i = 0; i <= 30; ++ i) { if (((_T >> i) & 1) && n->thb[i] == 0) r += (LL) k << i; if (((_T >> i) & 1) == 0 && n->thb[i]) r += (LL) k << i; } return r; } LL Q (int k) { if (k <= T) return Find (k); LL r = Find (T); k -= T; for (rg int i = 0; i <= 30; ++ i) if ((_T >> i) & 1) r += (LL) (k - s[k][i]) << i; else r += (LL) s[k][i] << i; return r; } void Cg (const int key) { _T ^= key; return ; } } D; int main (int argc, char *argv[]) { fread (buf, 1, BUF, stdin); int N, M, x, t, y; read (N); rg int i; for (i = 1; i <= N; ++ i) read (x), D.P (x); for (read (M); M; -- M) { read (t); if (t == 1) read (x), D.P (x ^ _T); else if (t == 3) read (x), read (y), printf ("%I64d ", D.Q(y) - D.Q(x - 1)); else if (t == 4) read (x), D.Cg (x); else D.ReBuild (); } return 0; }