前言
注意：以下的 “元素” 都代表原题中的一个操作。
大说
把当前值域一分为二，把当前元素集合，每个元素的决策只有左区间 or 右区间，可以把同决策的元素放在一起去分治子区间（类似于线段树的结构）。
如下图（左边是值域区间，右边是元素集合）：
上图每个询问的答案：
①：2
②：2
③：4
④：9
⑤：6
⑥：10
中说
那么怎么给元素们分决策呢？
首先我们二分值域区间，那么肯定有一个 \(mid\) ！
然后我们用 \(f(mid,i)\) 与 \(g(i)\) 比较来进行分配 \(i\) 元素去处。
以区间第 k 大举例：
一个元素 \(i\) 包含 \(l_i、r_i、k_i\)，表示询问 \([l_i,r_i]\) 中第 \(k_i\) 大的数。
\(f(mid,i)\) 就是 \(mid\) 在 \([l_i,r_i]\) 区间有多少个数比他小。
\(g(i)\) 就是 \(k_i\)。
如果前者大，那么值域区间肯定为 \([l,mid]\)，决策至左。
如果后者大，那么值域区间肯定为 \([mid+1,r]\)，决策至右。
小说：
【模板】带修整体二分
-
修改和询问一起放在元素集合里就行，修改如询问一般决策，所以这两个我都称作元素。
-
若询问元素决策到 \([mid+1,r]\) ，那么 \(k_i-=g(i)\)，因为关于 \(g(i)\) 的修改都决策到 \([l,mid]\) 了。
-
遇到修改就修改，遇到询问就询问。在顺序把每个元素决策到两个子区间时，子区间内各元素之间不会改变相对位置，所以可以带修。
#include<bits/stdc++.h>
using namespace std;
const int QAQ=510000;
int s[QAQ],n,m,ans[QAQ],cnt,shang[QAQ],a[QAQ];
int lbd(int x) {return (x&(-x));}
void gai(int x,int c) {for(int i=x;i<=n;i+=lbd(i)) s[i]+=c;}
int cha(int x) {int da=0;for(int i=x;i;i-=lbd(i)) da+=s[i];return da;}
char op;
struct xxx {int op,id,x,y,k;} q[QAQ],q1[QAQ],q2[QAQ];
void work(int l,int r,int ql,int qr)
{if(ql>qr) return ;if(l==r) {for(int i=ql;i<=qr;i++) if(q[i].op==0) ans[q[i].id]=l;return ;}int o1=0,o2=0,mid=(l+r)>>1;for(int i=ql;i<=qr;i++)if(q[i].op==0){int pai=cha(q[i].y)-cha(q[i].x-1);if(q[i].k<=pai) q1[++o1]=q[i];else q[i].k-=pai,q2[++o2]=q[i];}else{if(q[i].y<=mid) q1[++o1]=q[i],gai(q[i].x,q[i].k);else q2[++o2]=q[i];}for(int i=1;i<=o1;i++) if(q1[i].op) gai(q1[i].x,-q1[i].k);for(int i=1;i<=o1;i++) q[ql+i-1]=q1[i];for(int i=1;i<=o2;i++) q[ql+o1+i-1]=q2[i];work(l,mid,ql,ql+o1-1),work(mid+1,r,ql+o1,qr);
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i],q[++cnt]={1,114514,i,a[i],1},shang[i]=a[i];for(int i=1,l,r,k,x,y;i<=m;i++){ans[i]=-114514,cin>>op;if(op=='Q') cin>>l>>r>>k,q[++cnt]={0,i,l,r,k};else cin>>x>>y,q[++cnt]={1,114514,x,shang[x],-1},q[++cnt]={1,114514,x,y,1},shang[x]=y;}work(0,1000000000,1,cnt);for(int i=1;i<=m;i++) if(ans[i]!=-114514) cout<<ans[i]<<'\n';return 0;
}复杂度
可以发现多个二分答案的路径不过是 \(V log V\) 种，但是我只走 \(q\) 个路径所以我普通二分是 \(q log V\) 种路径都走一遍，但是我整体二分相当于路径重复的可以不算，所以可以想到用极限法证明：
极限法：所有点相距都一样远，并且尽可能地远，这样路径重复最少，是整体二分最绝望的时刻。
令 \(T(q,V)\) 为 \(q\) 个元素，\(V\) 大的值域的时间复杂度。
设 \(c(q)\) 是当前有 \(q\) 个元素继续分组分治花费的时间复杂度。
\(T(q,V)=2T(q/2,V/2)+c(q)\)
\(T(q,V)=\sum _{i}2^ic(\dfrac{q}{2^{i}})\)
\(T(q,V)≈\sum _{i}c(q)\) —— 因为 \(c(q)\) 一般是 \(q\log q\) 或者 \(q\)，所以可以这么算。
\([T(q,V)]_{max}=c(q)\log V\)
再看看此时二分什么复杂度：\(O(q·c(1)\log V)\) ，有时二分的 \(c(1)\) 的复杂度有时改得更快（如简单二分的 \(c(1)\) 是 \(O(1)\) 的，这时二分是 \(O(qlog V)\)，但是感觉整体二分在所有查询一起查询时更牛王。
