整体二分解决的最基本的问题是动态区间\(k\)小。
问题
对于\(n\)个元素的序列，支持两种操作，共\(m\)次：
Q l r k，询问\([l, r]\)区间内的第\(k\)小值C p x，将\(p\)位置修改成\(x\)
\(n, m \leq 10^5\)
解决方法
对于单个询问可以二分答案，但是对于\(m\)个询问复杂度太高，不能接受。
考虑如果有\(n\)个数进行排序，可以选定一个\(mid\)值，然后把比\(mid\)值小的元素放到左边，比\(mid\)值大的元素放在右边，然后递归处理。
在此基础上解决询问。把修改和询问放进一个数组去处理。首先读入原序列，全部当成修改来处理。如果后面还有修改，就把原来的值减掉，加上新值。具体流程见下
流程：
- 如果当前\(l = r\)，那么直接把当前边界内的询问的答案全部设为\(l\)即可。
- 设置\(mid = {(l + r) \over 2}\)遍历当前边界内的询问和修改
- 对于修改，如果修改的值小于等于\(mid\)，则在树状数组内给修改的位置+1，扔进左边，否则直接扔进右边。
- 对于询问，在树状数组内查询\([l, r]\)区间的和 （查到的是\([l, r]\)区间内比\(mid\)小的元素的个数，或者说是\(mid\)的排名），设为\(rnk\) 如果\(rnk \leq k\)，说明小于等于\(mid\)的元素不够\(k\)个，答案一定大于\(mid\)，扔到右边，并把\(k\)减去得到的值 （相当于在大于\(mid\)的区间里找第\(k-rnk\)个） 否则小于等于\(mid\)的元素多于\(k\)个，答案小于等于\(mid\)，扔到左边
- 最后清空树状数组，分治处理左边和右边的元素即可。
代码：
操作type为0是修改，l表示位置，r表示是删除原来的还是改成新的元素，k是值。type为1是查询，l, r是查询区间，k表示要查询的序号。 #include#include #include #include using namespace std;typedef long long ll;const int N = 100005, QUE = 300005;const bool Query = 1, Edit = 0;template inline void in(T &x){ //Read Positive Integer. register char ch; x = 0; while(isspace(ch = getchar())); do x = x * 10 + ch - '0'; while(isdigit(ch = getchar()));}inline char gvc(){ register char ch; while(isspace(ch = getchar())); return ch;}struct op{ bool type; int l, r, k, id; op(bool Type, int L, int R, int K, int Id): type(Type), l(L), r(R), k(K), id(Id){} op(){type = 0; l = r = k = id = 0;}}q[QUE], q1[QUE], q2[QUE]; //q1, q2用来临时存左边，右边的操作int a[N], ans[N], tr[N];int n, m, maxx;//树状数组操作void add(int p, int x){for(int i=p; i<=n; i+=i&(-i)) tr[i] += x;}int ask(int p){ int ans = 0; for(int i=p; i; i-=i&(-i)) ans += tr[i]; return ans;}void solve(int l, int r, int ql, int qr){ //l, r是答案区间，ql, qr表示待解决的操作 if(l == r){ for(int i=ql; i<=qr; i++) if(q[i].type == Query) ans[q[i].id] = l; return ; } else if(ql > qr) return ; int mid = (l + r) >> 1; int l1 = 0, l2 = 0; for(int i=ql; i<=qr; i++){ if(q[i].type == Edit){ if(q[i].k <= mid) add(q[i].l, q[i].r), q1[++l1] = q[i]; //小于等于mid才进树状数组 else q2[++l2] = q[i]; } else{ //QUERY int rnk = ask(q[i].r) - ask(q[i].l - 1); //查询区间中小于等于mid的元素个数，即mid的排名 if(q[i].k <= rnk) q1[++l1] = q[i]; else q[i].k -= rnk, q2[++l2] = q[i]; } } for(int i=1; i<=l1; i++){ if(q1[i].type == Edit && q1[i].k <= mid) add(q1[i].l, -q1[i].r); q[ql+i-1] = q1[i]; } for(int i=1; i<=l2; i++){ q[ql + l1 + i - 1] = q2[i]; } solve(l, mid, ql, ql+l1-1); solve(mid+1, r, ql+l1, qr);}int main(){ int len = 0, x, l, r, cnt = 0; in(n); in(m); for(int i=1; i<=n; i++){ in(a[i]); maxx = max(maxx, a[i]); q[++len] = op(Edit, i, 1, a[i], i); } for(int i=1; i<=m; i++){ if(gvc() == 'Q'){ in(l); in(r); in(x); q[++len] = op(Query, l, r, x, ++cnt); } else{ in(l); in(x); maxx = max(maxx, x); q[++len] = op(Edit, l, -1, a[l], i); //删掉原来的 a[l] = x; q[++len] = op(Edit, l, 1, a[l], i); //放进新的 } } solve(0, maxx, 1, len); for(int i=1; i<=cnt; i++) printf("%d\n", ans[i]); return 0;}