ZOJ 2112
題意
給你n個數，有q次操作，每次操作可以修改某一個數，或是求區間第k小值。（多組數據）
樣例輸入
2 5 3 3 2 1 4 7 Q 1 4 3 C 2 6 Q 2 5 3 5 3 3 2 1 4 7 Q 1 4 3 C 2 6 Q 2 5 3
樣例輸出
3 6 3 6
SOL
如果不考慮單點修改就是主席樹裸題。主席樹本質上使用前綴和維護的，查詢復雜度為O(1)，但修改復雜度為O(n)。如果不用前綴和，查詢復雜度為O(n)，修改復雜度為O(n)。（這不是廢話么…） 考慮在外面套上一層樹狀數組，使得查詢和修改復雜度均為O(logn)。
簡單的實現方式
普通的樹狀數組的每一個點存的都是某幾個數的和（和lowbit有關），那么本道題的每一個點存的都是一棵線段樹，并且相鄰線段樹之間用主席樹的方式連接。
時間復雜度分析
修改：每次最多對log(n)棵線段樹修改，每個節點中存的線段樹要修改log(n)次，最多加入(n+m)個數（最開始要放入n個數），所以時間復雜度為O((n+m)lognlogn)。 查詢：每次需要累加最多log(n)棵線段樹，每棵線段樹累加log(n)個節點，所以時間復雜度為O(mlognlogn)。
空間復雜度分析
每次操作修改log(n)棵線段樹，每棵線段樹修改log(n)個節點，所以空間復雜度為O((n+m)lognlogn)。
從這里可以可以看出時間復雜度和空間復雜度都是nlognlogn級別的，但是在ZOJ上內存限制只有64M，也就是說這種方式會MLE，如何解決？
靜態建樹+動態修改
分析數據范圍可以看出這道題目的m比較小，所以可以選擇一種神奇的方法：把查詢的區間分為兩步，第一步求出原區間，第二步加上修改的增量。第一步顯然就是裸的主席樹，第二步也就是沒有初值的修改，不同之處在于只要修改m就可以了?？臻g復雜度級數沒有變，但是常數大概能小4~6倍，空間剛好可以卡過去。下面就用這種方法具體解釋如何實現。
建樹
為了自己能夠更好的掌握，這里的建樹和更新方法都采用裸二叉樹的方法。（還有許多方法，比如不需要用遞歸實現的，以后有空可以學習一下，基本上遞歸方式能夠看懂非遞歸方式就很簡單了）
void build(int l,int r,int &rt){ rt = ++tot; sum[rt] = 0; if (l == r) return; int m = (l + r) >> 1; build(l,m,ls[rt]); build(m+1,r,rs[rt]);}更新
void update(int l,int r,int &rt,int last,int p,int delta){ rt = ++tot; ls[rt] = ls[last]; rs[rt] = rs[last]; sum[rt] = sum[last] + delta; if (l == r) return; int m = (l + r) >> 1; if (p <= m) update(l,m,ls[rt],ls[last],p,delta); else update(m+1,r,rs[rt],rs[last],p,delta);}查詢
個人感覺最難的部分就是查詢。從這里可以看出非遞歸方式寫起來真的非常清爽。。。特別是當樹套樹一層一層搞不清楚的時候寫成遞歸真的要死。。。 這里的S數組存的是樹狀數組里面每個節點代表的線段樹的根的編號（可以對比：root數組存的是原始數組里面每個節點代表的線段樹的根的編號），怎么更新S后面會講到。use1/2數組存的就是L-1和R的lowbit路徑。 int cnt = value2(R) - value1(L-1) + sum[ls[rrt]] - sum[ls[lrt]];這句話就是我剛才提到的“把查詢的區間分為兩步，第一步求出原區間，第二步加上修改的增量”。顯然value過程求的是增量，sum數組顯然是原區間的情況。
int value1(int x){ int re = 0; while (x > 0) {re += sum[ls[use1[x]]]; x -= lowbit(x);} return re;}int value2(int x){ int re = 0; while (x > 0) {re += sum[ls[use2[x]]]; x -= lowbit(x);} return re;}int Query(int L,int R,int k){ int lrt = root[L-1]; int rrt = root[R]; int l = 1,r = mm; for (int i = L - 1;i ; i -= lowbit(i)) use1[i] = S[i]; for (int i = R;i ; i -= lowbit(i)) use2[i] = S[i]; while (l < r) { int m = (l + r) >> 1; int cnt = value2(R) - value1(L-1) + sum[ls[rrt]] - sum[ls[lrt]]; if (k <= cnt) { r = m; for (int i = L - 1;i ; i -= lowbit(i)) use1[i] = ls[use1[i]]; for (int i = R;i ; i -= lowbit(i)) use2[i] = ls[use2[i]]; lrt = ls[lrt]; rrt = ls[rrt]; } else { l = m + 1; k = k - cnt; for (int i = L - 1;i > 0; i -= lowbit(i)) use1[i] = rs[use1[i]]; for (int i = R;i > 0; i -= lowbit(i)) use2[i] = rs[use2[i]]; lrt = rs[lrt]; rrt = rs[rrt]; } } return l;}修改
S數組一開始全部連到root[0]上表示全部為空。接下來每次修改一個數就新開一棵線段樹并且用S記錄位置。
void change(int x,int p,int delta){ while (x<=n) { update(1,k,S[x],S[x],p,delta); x += lowbit(x); }}完整代碼
#include<cmath>#include<cstdio>#include<vector>#include<cstring>#include<iomanip>#include<stdlib.h>#include<iostream>#include<algorithm>#define ll long long#define inf 1000000000#define mod 1000000007#define N 2500010#define M 60010using namespace std;struct data{int kind,l,r,k;}query[10010];char op[10];int T,n,mm,q,i,tot,k;int a[M],b[M],sum[N],ls[N],rs[N],root[M],S[M],use1[M],use2[M];void build(int l,int r,int &rt){ rt = ++tot; sum[rt] = 0; if (l == r) return; int m = (l + r) >> 1; build(l,m,ls[rt]); build(m+1,r,rs[rt]);}void update(int l,int r,int &rt,int last,int p,int delta){ rt = ++tot; ls[rt] = ls[last]; rs[rt] = rs[last]; sum[rt] = sum[last] + delta; if (l == r) return; int m = (l + r) >> 1; if (p <= m) update(l,m,ls[rt],ls[last],p,delta); else update(m+1,r,rs[rt],rs[last],p,delta);}int lowbit(int x){return x&(-x);}int value1(int x){ int re = 0; while (x > 0) {re += sum[ls[use1[x]]]; x -= lowbit(x);} return re;}int value2(int x){ int re = 0; while (x > 0) {re += sum[ls[use2[x]]]; x -= lowbit(x);} return re;}int Query(int L,int R,int k){ int lrt = root[L-1]; int rrt = root[R]; int l = 1,r = mm; for (int i = L - 1;i ; i -= lowbit(i)) use1[i] = S[i]; for (int i = R;i ; i -= lowbit(i)) use2[i] = S[i]; while (l < r) { int m = (l + r) >> 1; int cnt = value2(R) - value1(L-1) + sum[ls[rrt]] - sum[ls[lrt]]; if (k <= cnt) { r = m; for (int i = L - 1;i ; i -= lowbit(i)) use1[i] = ls[use1[i]]; for (int i = R;i ; i -= lowbit(i)) use2[i] = ls[use2[i]]; lrt = ls[lrt]; rrt = ls[rrt]; } else { l = m + 1; k = k - cnt; for (int i = L - 1;i > 0; i -= lowbit(i)) use1[i] = rs[use1[i]]; for (int i = R;i > 0; i -= lowbit(i)) use2[i] = rs[use2[i]]; lrt = rs[lrt]; rrt = rs[rrt]; } } return l;}void change(int x,int p,int delta){ while (x<=n) { update(1,k,S[x],S[x],p,delta); x += lowbit(x); }}int hash(int x){ return lower_bound(b+1,b+k+1,x)-b;}int main(){ cin>>T; while (T--) { cin>>n>>q; for (i = 1;i <= n; i++) scanf("%d",&a[i]); for (i = 1;i <= n; i++) b[i] = a[i]; k = n; for (i = 1;i <= q; i++) { scanf("%s",op); if (op[0] == 'Q') { query[i].kind = 0; scanf("%d%d%d",&query[i].l,&query[i].r,&query[i].k); } else { query[i].kind = 1; scanf("%d%d",&query[i].l,&query[i].r); b[++k] = query[i].r; } } sort(b+1,b+k+1); k = unique(b+1,b+k+1) - (b+1); tot = 0; build(1,k,root[0]); for (i = 1;i <= n; i++) update(1,k,root[i],root[i-1],hash(a[i]),1); for (i = 1;i <= n; i++) S[i] = root[0]; mm = k; for (i = 1;i <= q; i++) { if (query[i].kind == 0)
