动态第k大，第k小，离线下来。
考虑第k小怎么求，二分一个数值，然后扫一遍有多少小于等于 \(mid\) 的。一次nlogn,多次\(n^2log\)，既然你的是我的，我的就是你的，你做的就是我做的，我做的就是你做的，如果我做了，你又做，不就冗余了吗，那么就能一起二分，这样就是\(nlogn\)。怎么一起，还是枚举一个值，然后扫一下序列，有cnt个小于等于mid，把k小于等于cnt划分到左边，其余的划分到右边，分治，用线段树分析一波，就是\(nlogn\)。注意如果[l,mid],[mid + 1,r]有一个为空了，及时return，保证时间复杂度。就好像线段树单点修改本来是log的，如果左右儿子都扫，变成nlogn。
动态,就是多了一个修改，添加。
点击查看代码
void solve(int l,int r,int L,int R){
if(L > R)return;
if(l == r){
for(int i = L;i <= R;++i)if(q[i].opt == 1)ans[q[i].id] = l;
return;
}
int mid = l + r >> 1,ed1 = 0,ed2 = 0;
for(int i = L;i <= R;++i){
if(q[i].opt == 0){
if(q[i].l <= mid){
T.add(q[i].r,q[i].k);
q1[++ed1] = q[i];
}else q2[++ed2] = q[i];
}else{
int t = T.ask(q[i].r) - T.ask(q[i].l - 1);
if(q[i].k <= t){
q1[++ed1] = q[i];
}else q[i].k -= t,q2[++ed2] = q[i];
}
}
for(int i = 1;i <= ed1;++i)if(q1[i].opt == 0)T.add(q1[i].r,-q1[i].k);
for(int i = 1;i <= ed1;++i)q[L + i - 1] = q1[i];
for(int i = 1;i <= ed2;++i)q[L + ed1 + i - 1] = q2[i];
solve(l,mid,L,L + ed1 - 1);
solve(mid + 1,r,L + ed1,R);
}