bzoj3110(整体二分)

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=50010;
typedef long long ll;
int n,m;
struct bit{
    ll tr[maxn];
    void add(int pos,ll v){
        for(int i=pos;i<maxn;i+=i&(-i))tr[i]+=v;
    }
    ll qs(int pos){
        ll res=0;
        for(int i=pos;i;i-=i&(-i))res+=tr[i];
        return res;
    }
}A,B;
void update(int l,int r,ll v){
    A.add(r,v*r);A.add(l-1,-v*(l-1));
    B.add(r,v);B.add(l-1,-v);
}
ll query(int l,int r){
    ll tt1=(B.qs(n+1)-B.qs(r))*r+A.qs(r);
    ll tt2=(B.qs(n+1)-B.qs(l-1))*(l-1)+A.qs(l-1);
    return tt1-tt2;
}
struct ope{
    int id,op,a,b;
    ll c;
}t[maxn],tmp1[maxn],tmp2[maxn],tt[maxn];
ll C;
int ans[maxn];
void solve(int l,int r,int L,int R){//L和R是当前二分的答案，l和r是当前区间； 
    if(l>r)return;
    //cout<<l<<' '<<r<<endl;
    if(L==R){
        for(int i=l;i<=r;++i){
            if(t[i].op==2)ans[t[i].id]=L;
        }
        return;
    } 
    int mid=L+R>>1;
    int t1=0,t2=0;//注意这里设局部变量； 
    for(int i=l;i<=r;++i){
        if(t[i].op==1){
            if(t[i].c>mid){
                update(t[i].a,t[i].b,1);
                tmp2[++t2]=t[i];
            }
            else tmp1[++t1]=t[i];
        }
        else{
            ll cc=query(t[i].a,t[i].b);
            //cout<<t[i].a<<' '<<t[i].b<<' '<<cc<<endl;
            if(cc>=t[i].c)tmp2[++t2]=t[i];
            else {
                tmp1[++t1]=t[i];tmp1[t1].c-=cc;
            }
        }
    }
    for(int i=l;i<=r;++i){
        if(t[i].op==1){
            if(t[i].c>mid)update(t[i].a,t[i].b,-1);
        }
    }
    for(int i=1;i<=t1;++i)t[l+i-1]=tmp1[i];
    for(int i=1;i<=t2;++i)t[l+i+t1-1]=tmp2[i];
    //cout<<l<<' '<<r<<endl;
    /*cout<<l<<' '<<l+t1-1<<' '<<L<<' '<<mid<<endl;
    cout<<l+t1<<' '<<r<<' '<<mid+1<<' '<<R<<endl;
    cout<<endl;*/
    solve(l,l+t1-1,L,mid);solve(l+t1,r,mid+1,R);
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        t[i].id=i;
        scanf("%d%d%d%lld",&t[i].op,&t[i].a,&t[i].b,&t[i].c);
        t[i].a++;t[i].b++;
        C=max(C,t[i].c);
    }
    for(int i=1;i<=m;++i)tt[i]=t[i];
    solve(1,m,0,C);
    for(int i=1;i<=m;++i)
    if(tt[i].op==2)printf("%d
",ans[i]);
    return 0;
}