20200903 专题：值域分块

总览：

做了一道毒瘤题 带插区间k小 并且树套树常数过大，过不去 （毒瘤出题人毒瘤卡常） 于是就学习了新科技：值域分块

实质是分块套分块，先给序列分块，再在每个块中给值域分块 （分块用链表实现好方便 具体题目具体分析

T1 P4278 带插入区间K小值

思路： bzoj一个点平均15s，luogu一个点1s……

先对序列分块，方便取出 $[l,r]$ 再对值域分块，方便查询 $k$ 小 要 $O(1)$ 查询 $[l,r]$ 中值在 $[va{l}_l,va{l}_r]$ 中的数的个数 于是可以对值域做序列上的前缀和 查询时先 $O(\sqrt{n})$ 将块取出，再 $O(\sqrt{n})$ 找到 $k$ 小 修改，插入时要更新每个序列块中一个值域块前缀和，$O(\sqrt{n})$ 如果在一个块中插入过多，将这个块分裂成两个块即可

块状链表实现 找个人少的时候卡过去

代码：

#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize("Ofast") #pragma GCC optimize("inline") #pragma GCC optimize("-fgcse") #pragma GCC optimize("-fgcse-lm") #pragma GCC optimize("-fipa-sra") #pragma GCC optimize("-ftree-pre") #pragma GCC optimize("-ftree-vrp") #pragma GCC optimize("-fpeephole2") #pragma GCC optimize("-ffast-math") #pragma GCC optimize("-fsched-spec") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("-falign-jumps") #pragma GCC optimize("-falign-loops") #pragma GCC optimize("-falign-labels") #pragma GCC optimize("-fdevirtualize") #pragma GCC optimize("-fcaller-saves") #pragma GCC optimize("-fcrossjumping") #pragma GCC optimize("-fthread-jumps") #pragma GCC optimize("-funroll-loops") #pragma GCC optimize("-fwhole-program") #pragma GCC optimize("-freorder-blocks") #pragma GCC optimize("-fschedule-insns") #pragma GCC optimize("inline-functions") #pragma GCC optimize("-ftree-tail-merge") #pragma GCC optimize("-fschedule-insns2") #pragma GCC optimize("-fstrict-aliasing") #pragma GCC optimize("-fstrict-overflow") #pragma GCC optimize("-falign-functions") #pragma GCC optimize("-fcse-skip-blocks") #pragma GCC optimize("-fcse-follow-jumps") #pragma GCC optimize("-fsched-interblock") #pragma GCC optimize("-fpartial-inlining") #pragma GCC optimize("no-stack-protector") #pragma GCC optimize("-freorder-functions") #pragma GCC optimize("-findirect-inlining") #pragma GCC optimize("-fhoist-adjacent-loads") #pragma GCC optimize("-frerun-cse-after-loop") #pragma GCC optimize("inline-small-functions") #pragma GCC optimize("-finline-small-functions") #pragma GCC optimize("-ftree-switch-conversion") #pragma GCC optimize("-foptimize-sibling-calls") #pragma GCC optimize("-fexpensive-optimizations") #pragma GCC optimize("-funsafe-loop-optimizations") #pragma GCC optimize("inline-functions-called-once") #pragma GCC optimize("-fdelete-null-pointer-checks") #include <bits/stdc++.h> using namespace std; #define re register namespace IO { char _buf[1 << 21], *_p1 = _buf, *_p2 = _buf; #define ch() \ (_p1 == _p2 && \ (_p2 = (_p1 = _buf) + fread(_buf, 1, 1 << 21, stdin), _p1 == _p2) \ ? EOF \ : *_p1++) inline int in() { int s = 0, f = 1; char x = ch(); for (; x < '0' || x > '9'; x = ch()) if (x == '-') f = -1; for (; x >= '0' && x <= '9'; x = ch()) s = (s * 10) + (x & 15); return f == 1 ? s : -s; } char buf_[1 << 21]; int p_ = -1; inline void flush() { fwrite(buf_, 1, p_ + 1, stdout); p_ = -1; } inline void pc(char x) { if (p_ == (1 << 21) - 1) flush(); buf_[++p_] = x; } inline void out(int x) { char k[30]; int pos = 0; if (!x) { pc('0'); return; } if (x < 0) { pc('-'); x = -x; } while (x) { k[++pos] = (x % 10) | 48; x /= 10; } for (int i = pos; i; i--) pc(k[i]); return; } } // namespace IO using namespace IO; const int A = 7e4; const int SA = 275; int n, blo, Q; struct block { int ls, rs, sz; int s[(SA << 1) + 50], v[SA + 10], w[A + 10]; } t[SA + 10]; int rt, tot; int ans; #define ls(x) t[x].ls #define rs(x) t[x].rs inline void prepare() { n = in(); rt = 0, tot = n / SA + 1; for (int i = 1; i <= n; i++) { int u = in(), now = i / SA + 1; t[now].s[++t[now].sz] = u; t[now].w[u]++, t[now].v[u / SA + 1]++; } for (int i = 0; i <= tot; i++) { if (i) { ls(i) = i - 1; for (int j = 0; j <= A; j++) t[i].w[j] += t[i - 1].w[j]; for (int j = 1; j <= SA; j++) t[i].v[j] += t[i - 1].v[j]; } if (i != tot) rs(i) = i + 1; } return; } inline void split(int now) { t[++tot] = t[now]; ls(tot) = ls(now), rs(tot) = now; rs(ls(now)) = tot, ls(now) = tot; for (int i = SA + 1; i <= t[now].sz; i++) { int k = t[now].s[i]; t[now].s[i - SA] = k; t[tot].w[k]--; t[tot].v[k / SA + 1]--; } t[tot].sz = SA, t[now].sz -= SA; return; } inline void insert(int x, int k) { int now = rs(rt); while (x - 1 > t[now].sz) x -= t[now].sz, now = rs(now); t[now].sz++; for (int i = t[now].sz; i > x; i--) t[now].s[i] = t[now].s[i - 1]; t[now].s[x] = k; int tmp = now; while (now) { t[now].w[k]++, t[now].v[k / SA + 1]++; now = rs(now); } if (t[tmp].sz >= (SA << 1)) split(tmp); } inline void change(int x, int k) { int now = rs(rt); while (x > t[now].sz) x -= t[now].sz, now = rs(now); int u = t[now].s[x]; t[now].s[x] = k; while (now) { t[now].w[u]--, t[now].w[k]++; t[now].v[u / SA + 1]--, t[now].v[k / SA + 1]++; now = rs(now); } return; } int V[SA], W[A]; inline int qurey(int x, int y, int k) { int l = rs(rt), r = rs(rt); while (x > t[l].sz) x -= t[l].sz, l = rs(l); while (y > t[r].sz) y -= t[r].sz, r = rs(r); for (int i = 1; i < x; i++) { int u = t[l].s[i]; W[u]--, V[u / SA + 1]--; } for (int i = 1; i <= y; i++) { int u = t[r].s[i]; W[u]++, V[u / SA + 1]++; } int now = 1; while (k > V[now] + (t[ls(r)].v[now] - t[ls(l)].v[now])) k -= V[now] + (t[ls(r)].v[now] - t[ls(l)].v[now]), now++; int res = SA * (now - 1); while (k > W[res] + (t[ls(r)].w[res] - t[ls(l)].w[res])) k -= W[res] + (t[ls(r)].w[res] - t[ls(l)].w[res]), res++; for (int i = 1; i < x; i++) { int u = t[l].s[i]; W[u]++, V[u / SA + 1]++; } for (int i = 1; i <= y; i++) { int u = t[r].s[i]; W[u]--, V[u / SA + 1]--; } return res; } #undef ls #undef rs signed main() { prepare(); Q = in(); while (Q--) { char opt = ch(); while (opt != 'Q' && opt != 'M' && opt != 'I') opt = ch(); if (opt == 'Q') { int u = in() ^ ans, v = in() ^ ans, k = in() ^ ans; out(ans = qurey(u, v, k)), pc('\n'); } else if (opt == 'M') { int u = in() ^ ans, k = in() ^ ans; change(u, k); } else { int u = in() ^ ans, k = in() ^ ans; insert(u, k); } } flush(); return 0; }