求助的第三个帖子

码风有点丑，且线段树和大家写的有点不一样。。。

8pts

#include<bits/stdc++.h>
#define ll long long
#define lid id<<1
#define rid (lid)+1
using namespace std;
const int N=100005;
int n,m,op,x,y;
ll k;
struct tree
{
    int l,r;
    ll sum,suml,sumr,lz;
}tr[N<<2];
void build(int l,int r,int id)
{
    tr[id].l=l,tr[id].r=r,tr[id].lz=0,tr[id].sum=tr[id].suml=tr[id].sumr=r-l+1;
    if(l==r)return;
    int mid=(l+r)>>1;
    build(l,mid,lid);
    build(mid+1,r,rid);
}
void pd(int id)
{
    if(tr[id].lz==0)return;
    tr[lid].sum=tr[lid].suml=tr[lid].sumr=\
    tr[rid].sum=tr[rid].suml=tr[rid].sumr=\
    tr[id].sum=tr[id].suml=tr[id].sumr=tr[id].lz==1?0:tr[id].r-tr[id].l+1;
    tr[lid].lz=tr[rid].lz=tr[id].lz,tr[id].lz=0;
}
void mdf(int l,int r,int id,int zt)
{
    if(r<l)return;
    if(tr[id].l==l&&tr[id].r==r)
    {
        tr[id].lz=zt;
        tr[lid].sum=tr[lid].suml=tr[lid].sumr=\
        tr[rid].sum=tr[rid].suml=tr[rid].sumr=\
        tr[id].sum=tr[id].suml=tr[id].sumr=tr[id].lz==1?0:tr[id].r-tr[id].l+1;
        return;
    }
    pd(id);
    if(tr[lid].r>=l)
    {
        if(tr[rid].l<=r)
        {
            mdf(l,tr[lid].r,lid,zt);
            mdf(tr[rid].l,r,rid,zt);
        }
        else mdf(l,r,lid,zt);
    }
    else mdf(l,r,rid,zt);
    tr[id].sum=max(max(tr[lid].sum,tr[rid].sum),tr[lid].sumr+tr[rid].suml);
    tr[id].suml=(tr[lid].sum==tr[lid].r-tr[lid].l+1?tr[lid].sum+tr[rid].suml:tr[lid].suml);
    tr[id].sumr=(tr[rid].sum==tr[rid].r-tr[rid].l+1?tr[rid].sum+tr[lid].sumr:tr[rid].sumr);
}
ll query(int l,int r,int id)
{
    pd(id);
    if(l==r)return l;
    if(tr[lid].sum>=x)return query(l,tr[lid].r,lid);
    if(tr[lid].sumr+tr[rid].suml>=x)return tr[lid].r-tr[lid].sumr+1;
    return query(tr[rid].l,r,rid);
}
int main()
{
    //freopen("P2894_2.in","r",stdin);
    //freopen("1.out","w",stdout);
    cin>>n>>m;
    build(1,n,1);
    while(m--)
    {
        scanf("%d%d",&op,&x);
        if(op==2)
        {
            scanf("%d",&y);
            mdf(x,x+y-1,1,2);
        }
        else
        {
            if(tr[1].sum>=x)
            {
                int t=query(1,n,1);
                printf("%d\n",t);
                mdf(t,t+x-1,1,1);
            }
            else puts("0");
        }
        //for(int i=1;i<=n<<1;i++)printf("%d %d %d %d %d %d\n",tr[i].l,tr[i].r,tr[i].sum,tr[i].suml,tr[i].sumr,tr[i].lz);
        //printf("\n");
    }
    return 0;
}