思路：

外围一个权值线段树

里面是个区间线段树

搞一个标记永久化

//By SiriusRen

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define N 100050

#define int long long

int n,m,op,xx,yy,zz,cnt,root[N*16],lson[N*160],rson[N*160];

int tree[N*160],lazy[N*160];

void insert(int l,int r,int &rt){

    if(!rt)rt=++cnt;

    if(l>=xx&&r<=yy){tree[rt]+=r-l+1,lazy[rt]++;return;}

    int mid=(l+r)>>1;

    if(mid<xx)insert(mid+1,r,rson[rt]);

    else if(mid>=yy)insert(l,mid,lson[rt]);

    else insert(l,mid,lson[rt]),insert(mid+1,r,rson[rt]);

    tree[rt]+=(min(yy,r)-max(xx,l)+1);

}

void Insert(int l,int r,int pos){

    insert(1,n,root[pos]);

    if(l==r)return;

    int mid=(l+r)>>1,Lson=pos<<1,Rson=pos<<1|1;

    if(mid<zz)Insert(mid+1,r,Rson);

    else Insert(l,mid,Lson);

}

int query(int l,int r,int rt){

    if(!rt)return 0;

    if(l>=xx&&r<=yy)return tree[rt];

    int mid=(l+r)>>1,ret=0;

    if(mid>=xx)ret+=query(l,mid,lson[rt]);

    if(mid<yy)ret+=query(mid+1,r,rson[rt]);

    return ret+lazy[rt]*(min(yy,r)-max(xx,l)+1);

}

int Query(int l,int r,int pos){

    if(l==r){return l-50001;}

    int mid=(l+r)>>1,Lson=pos<<1,Rson=pos<<1|1;

    int res=query(1,n,root[Rson]);

    if(res>=zz)return Query(mid+1,r,Rson);

    else{zz-=res;return Query(l,mid,Lson);}

}

signed main(){

    scanf("%lld%lld",&n,&m);

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

        scanf("%lld%lld%lld%lld",&op,&xx,&yy,&zz);

        if(op==1)zz+=50001,Insert(1,N,1);

        else printf("%lld\n",Query(1,N,1));

    }

}