總覽：
做了一道毒瘤題 帶插區間k小
并且樹套樹常數過大，過不去 （毒瘤出題人毒瘤卡常）
于是就學習了新科技：值域分塊
實質是分塊套分塊，先給序列分塊，再在每個塊中給值域分塊
（分塊用連結清單實作好友善
具體題目具體分析
T1 P4278 帶插入區間K小值
思路：
bzoj一個點平均15s，luogu一個點1s……
先對序列分塊，友善取出 [ l , r ] [l,r] [l,r]
再對值域分塊，友善查詢 k k k 小
要 O ( 1 ) O(1) O(1) 查詢 [ l , r ] [l,r] [l,r] 中值在 [ v a l l , v a l r ] [val_l,val_r] [vall,valr] 中的數的個數
于是可以對值域做序列上的字首和
查詢時先 O ( n ) O(\sqrt n) O(n
) 将塊取出，再 O ( n ) O(\sqrt n) O(n
) 找到 k k k 小
修改，插入時要更新每個序列塊中一個值域塊字首和， O ( n ) O(\sqrt n) O(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;
}
![iPhone5搭載iOS6：App應用與Siri攻略[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)