只过hack和#11 ,铅条

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=50010;
int n,m,ans[N];
long long mi=9223372036854775807,ma=-9223372036854775807;
struct node{
	int l,r,id,opt,c;
}q[N],q1[N],q2[N];
struct nod{
	int v,add,lmf,rmf;
}tr[N*4];
void pushup(int root){
	tr[root].v=tr[root<<1].v+tr[(root<<1)+1].v;
	return ;
}
void pushdown(int root){
	if(!tr[root].add) return ;
	tr[root<<1].add+=tr[root].add;
	tr[(root<<1)+1].add+=tr[root].add;
	tr[root<<1].v+=tr[root].add*(tr[root<<1].rmf-tr[root<<1].lmf+1);
	tr[(root<<1)+1].v+=tr[root].add*(tr[(root<<1)+1].rmf-tr[(root<<1)+1].lmf+1);
	tr[root].add=0;
	return ;
}
void build(int root,int l1,int r1){
	tr[root].lmf=l1,tr[root].rmf=r1;
	if(l1==r1){
		return ;
	}
	int mid=(l1+r1)>>1;
	build(root<<1,l1,mid);
	build((root<<1)+1,mid+1,r1);
	return ;
}
void updata(int root,int l1,int r1,int vv){
	if(l1<=tr[root].lmf&&tr[root].rmf<=r1){
		tr[root].v+=(tr[root].rmf-tr[root].lmf+1)*vv;
		tr[root].add+=vv;
		return ;
	}
	pushdown(root);
	int mid=(tr[root].lmf+tr[root].rmf)>>1;
	if(l1<=mid) updata(root<<1,l1,r1,vv);
	if(r1>mid) updata((root<<1)+1,l1,r1,vv);
	pushup(root);
	return ;
}
int query(int root,int l1,int r1){
	if(l1<=tr[root].lmf&&tr[root].rmf<=r1){
		return tr[root].v;
	}
	pushdown(root);
	int mid=(tr[root].lmf+tr[root].rmf)>>1,s=0;
	if(l1<=mid) s+=query(root<<1,l1,r1);
	if(r1>mid) s+=query((root<<1)+1,l1,r1);
	return s;
}
void solve(int l1,int r1,int L,int R){
	if(l1>r1) return ;
	if(L==R){
		for(int i=l1;i<=r1;++i){ if(!(q[i].opt&1)) ans[q[i].id]=L;}
		return ;
	}
	int mid=L+(R-L)/2;
	int p1=0,p2=0;
	for(int i=l1;i<=r1;++i){
		if(q[i].opt&1){
			if(q[i].c>mid){
				q1[++p1]=q[i];
				updata(1,q[i].l,q[i].r,1);
			}
			else q2[++p2]=q[i];
		}
		else{
			int mfs=query(1,q[i].l,q[i].r);
			if(mfs>=q[i].c){
				q1[++p1]=q[i];
			}
			else{
				q[i].c-=mfs;
				q2[++p2]=q[i];
			}
		}
	}
	for(int i=1;i<=p1;++i){
		if(q1[i].opt&1){
			updata(1,q1[i].l,q1[i].r,-1);
		}
	}
	for(int i=1;i<=p1;++i) q[l1+i-1]=q1[i];
	for(int i=1;i<=p2;++i) q[l1+i+p1-1]=q2[i];
	solve(l1,l1+p1-1,mid+1,R);
	solve(l1+p1,r1,L,mid);
	return ;
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;++i){
		cin>>q[i].opt>>q[i].l>>q[i].r>>q[i].c;
		q[i].id=i;
		if(q[i].opt&1){
			mi=min(mi,q[i].c),ma=max(ma,q[i].c);
		}
	}
	build(1,1,n);
	solve(1,m,mi,ma);
	for(int i=1;i<=m;++i){
		if(!(q[i].opt&1)){
			cout<<ans[i]<<'\n';
		}
	}
	return 0;
}