首发题解

原题：P3332 [ZJOI2013] K大数查询
前置姿势：整体二分
注意到不能用普通 BIT 进行整体二分插入了，需要一种区间插入数据的数据结构。
没错！变体 BIT 线段树。
其实也就是换了一个方式实现。由于是线段树，我们不需要一个一个操作清空，而是直接用基础区间增加 d 和区间设为 d 的线段树，每次操作前给整个区间（节点1）打上清空 tag 就行啦。
注意到分治代码略有不同，这是因为求的是第 $k$ 大

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){
    int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void write(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar((x%10)|48);
}
const int N=50005;
int n,m,tree[N<<2],tag1[N<<2],ans[N],cnt;
bool tag2[N<<2];
struct order{
    int op,l,r,k,id;
}q[N],q1[N],q2[N];
void push_up(int p){tree[p]=tree[p<<1]+tree[p<<1|1];}
void addtag1(int p,int l,int r,int d){tree[p]+=d*(r-l+1);tag1[p]+=d;}
void addtag2(int p){tree[p]=tag1[p]=0,tag2[p]=1;}
void push_down(int p,int l,int r){
    if(tag2[p])addtag2(p<<1),addtag2(p<<1|1),tag2[p]=0;
    if(tag1[p]){
        int mid=l+r>>1;
        addtag1(p<<1,l,mid,tag1[p]),addtag1(p<<1|1,mid+1,r,tag1[p]);
        tag1[p]=0;
    }
}
void update(int p,int l,int r,int L,int R,int d){
    if(L<=l&&r<=R){addtag1(p,l,r,d);return;}
    push_down(p,l,r);
    int mid=l+r>>1;
    if(L<=mid)update(p<<1,l,mid,L,R,d);
    if(mid<R)update(p<<1|1,mid+1,r,L,R,d);
    push_up(p);
}
int query(int p,int l,int r,int L,int R){
    if(L<=l&&r<=R)return tree[p];
    push_down(p,l,r);
    int ans=0,mid=l+r>>1;
    if(L<=mid)ans+=query(p<<1,l,mid,L,R);
    if(mid<R)ans+=query(p<<1|1,mid+1,r,L,R);
    return ans;
}
void solve(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==2)
                ans[q[i].id]=l;
        return;
    }
    addtag2(1);
    int cnt1=0,cnt2=0,mid=l+r>>1;bool b1=0,b2=0;
    for(int i=ql;i<=qr;++i){
        if(q[i].op==1){
            if(q[i].k<=mid)q1[++cnt1]=q[i];
            else update(1,1,n,q[i].l,q[i].r,1),q2[++cnt2]=q[i];
        }
        else{
            int t=query(1,1,n,q[i].l,q[i].r);
            if(t>=q[i].k)q2[++cnt2]=q[i],b2=1;
            else q[i].k-=t,q1[++cnt1]=q[i],b1=1;
        }
    }
    for(int i=1;i<=cnt1;++i)q[ql+i-1]=q1[i];
    for(int i=1;i<=cnt2;++i)q[ql+cnt1+i-1]=q2[i];
    if(b1)solve(l,mid,ql,ql+cnt1-1);
    if(b2)solve(mid+1,r,ql+cnt1,qr);
}
signed main(){
    n=read(),m=read();
    for(int i=1;i<=m;++i)
        q[i]={read(),read(),read(),read(),0},q[i].id=q[i].op==1?0:++cnt;
    solve(-n,n,1,m);
    for(int i=1;i<=cnt;++i)
        write(ans[i]),putchar('\n');
    return 0;
}