线段树写的

#include<bits/stdc++.h>
#define Code using
#define by namespace
#define wjb std
Code by wjb;
int in()
{
	int k=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
	return k*f;
}
void out(int x)
{
	if(x<0)putchar('-'),x=-x;
	if(x<10)putchar(x+'0');
	else out(x/10),putchar(x%10+'0');
}
int tr[1600010],lazy[1600010];
void down(int x,int l,int r)
{
	tr[x]+=lazy[x]*(r-l+1);
	if(l<r)lazy[2*x]+=lazy[x],lazy[2*x+1]+=lazy[x];
	lazy[x]=0;
}
int maxx(int x,int l,int r,int le,int ri)
{
	if(le<=l&&ri>=r)return tr[x]+lazy[x]*(r-l+1);
	if(lazy[x])down(x,l,r);
	int ans=0;
	int mid=(l+r)>>1;
	if(le<=mid)ans=max(ans,maxx(2*x,l,mid,le,ri));
	if(ri>=mid+1)ans=max(ans,maxx(2*x+1,mid+1,r,le,ri));
	return ans;
}
void change(int x,int l,int r,int le,int ri,int q)
{
	if(le<=l&&ri>=r)
	{
		lazy[x]+=q;
		return;
	}
	if(lazy[x])down(x,l,r);
	int mid=(l+r)>>1;
	if(le<=mid)change(2*x,l,mid,le,ri,q);
	if(ri>=mid+1)change(2*x+1,mid+1,r,le,ri,q);
	int lt=tr[2*x]+lazy[2*x]*(mid-l+1);
	int rt=tr[2*x+1]+lazy[2*x+1]*(r-mid);
	tr[x]=max(lt,rt);
}
int num[400010],bh[400010];
multiset<int>s;
int two(int l,int r,int x)
{
    int ans=0;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(bh[mid]==x)return mid;
        else if(bh[mid]<x)ans=mid,l=mid+1;
        else r=mid-1;
    }
    return ans;
}
int main()
{
	int c=in(),q=in(),siz=0,h=1,z=0;
	int qq=q;
	while(q--)
	{
		int t=in();
		if(t==4)out(maxx(1,1,2*qq,h+1,siz)),putchar('\n');
		else
		{
			int x=in();
			if(t==1)
			{
				num[++siz]=1,bh[siz]=bh[siz-1]+1,change(1,1,2*qq,siz,siz,1);
				num[++siz]=x,bh[siz]=bh[siz-1]+x-1,change(1,1,2*qq,siz,siz,x);
			}
			else if(t==2)
			{
				z+=x;
				int s=0;
				for(;h<=siz;h+=2)
				{
					if(s+bh[h+1]-bh[h]+1>x)break;
					s+=bh[h+1]-bh[h]+1;
				}
				if(s!=x)num[h]+=x-s,change(1,1,2*qq,h,h,x-s),bh[h]+=x-s;
			}
			else
			{
				x+=z;
				int k=two(h,siz,x);
				out(num[k]+x-bh[k]),putchar('\n');
			}
		}
	}
	return 0;
}