bzoj3110(整体二分)

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=;

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=;

        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-,-v*(l-));

    B.add(r,v);B.add(l-,-v);

}

ll query(int l,int r){

    ll tt1=(B.qs(n+)-B.qs(r))*r+A.qs(r);

    ll tt2=(B.qs(n+)-B.qs(l-))*(l-)+A.qs(l-);

    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==)ans[t[i].id]=L;

        }

        return;

    }

    int mid=L+R>>;

    int t1=,t2=;//注意这里设局部变量；

    for(int i=l;i<=r;++i){

        if(t[i].op==){

            if(t[i].c>mid){

                update(t[i].a,t[i].b,);

                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==){

            if(t[i].c>mid)update(t[i].a,t[i].b,-);

        }

    }

    for(int i=;i<=t1;++i)t[l+i-]=tmp1[i];

    for(int i=;i<=t2;++i)t[l+i+t1-]=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-,L,mid);solve(l+t1,r,mid+,R);

}

int main(){

    cin>>n>>m;

    for(int i=;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=;i<=m;++i)tt[i]=t[i];

    solve(,m,,C);

    for(int i=;i<=m;++i)

    if(tt[i].op==)printf("%d\n",ans[i]);

    return ;

}