Description 給定一個含有n個數的序列a[1],a[2],a[3]……a[n]，程式必須回答這樣的詢問：對於給定的i,j,k，在a[i],a[i+1 ],a[i+2]……a[j]中第k小的數是多少(1≤k≤j-i+1)，並且，你可以改變一些a[i]的值，改變後，程式還能針對改 變後的a繼續 ...
Submit: 9094 Solved: 3808
[Submit][Status][Discuss]
Description
給定一個含有n個數的序列a[1],a[2],a[3]……a[n]，程式必須回答這樣的詢問：對於給定的i,j,k，在a[i],a[i+1 ],a[i+2]……a[j]中第k小的數是多少(1≤k≤j-i+1)，並且，你可以改變一些a[i]的值，改變後，程式還能針對改 變後的a繼續回答上面的問題。Input
第一行有兩個正整數n(1≤n≤10000)，m(1≤m≤10000)。 分別表示序列的長度和指令的個數。 第二行有n個數，表示a[1],a[2]……a[n]，這些數都小於10^9。 接下來的m行描述每條指令 每行的格式是下麵兩種格式中的一種。 Q i j k 或者 C i t Q i j k （i,j,k是數字，1≤i≤j≤n, 1≤k≤j-i+1） 表示詢問指令，詢問a[i]，a[i+1]……a[j]中第k小的數。 C i t (1≤i≤n，0≤t≤10^9)表示把a[i]改變成為t m,n≤10000Output
對於每一次詢問，你都需要輸出他的答案，每一個輸出占單獨的一行。
Sample Input
5 33 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
Sample Output
36
HINT
Source
整體二分真是個好東西啊，
而且特別好寫。
思想大概就是把所有的詢問全都放到一塊處理，然後剩下的就和普通的處理一樣了。
修改操作的話就是先刪除再增加
第$k$大為經典操作，每次找比當前小的有多少個的時候用樹狀數組維護
#include<cstdio> #include<cstring> #include<vector> #define lowbit(x) ((x) & (-x)) #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++) using namespace std; const int MAXN = 1e5 + 10, INF = 1e9 + 10; char buf[1 << 21], *p1 = buf, *p2 = buf; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } struct Query { int opt, l, r, k, id; }; vector<Query> Q; int N, M, a[MAXN], ans[MAXN], T[MAXN]; void Add(int pos, int val) { for(int i = pos; i <= N; i += lowbit(i)) T[i] += val;} int Sum(int pos) { int ans = 0; for(int i = pos; i > 0; i -= lowbit(i)) ans += T[i]; return ans; } void Solve(int lb, int rb, vector<Query> &Q) { if(Q.empty()) return ; if(rb - lb == 1) { for(int i = 0; i < Q.size(); i++) if(Q[i].opt == 1) ans[Q[i].id] = lb; return ; } vector<Query>L, R; int mid = (lb + rb) >> 1; for(int i = 0; i < Q.size(); i++) { Query p = Q[i]; if(p.opt == 0) {// l:pos r:opt k:val if(p.k < mid) Add(p.l, p.r), L.push_back(p); else R.push_back(p); } else {// l: Ql R: Ql k:you know int kth = Sum(p.r) - Sum(p.l - 1); if(kth >= p.k) L.push_back(p); else p.k -= kth, R.push_back(p); } } for(int i = 0; i < L.size(); i++) if(L[i].opt == 0) Add(L[i].l, -L[i].r); Solve(lb, mid, L); Solve(mid, rb, R); } main() { N = read(); M = read(); for(int i = 1; i <= N; i++) Q.push_back((Query){0, i, 1, a[i] = read(), 0}); for(int i = 1; i <= M; i++) { char c = '_';while(c != 'C' && c != 'Q') c = getchar(); if(c == 'C') { int pos = read(), val = read(); Q.push_back((Query){0, pos, -1, a[pos], 0}); Q.push_back((Query){0, pos, 1, a[pos] = val, 0}); } else { int ll = read(), rr = read(), kth = read(); Q.push_back((Query){1, ll, rr, kth, i}); } } memset(ans, -0x3f, sizeof(ans)); Solve(0, 1e9, Q); for(int i = 1; i <= M; i++) if(ans[i] >= -INF) printf("%d\n", ans[i]); return 0; }
