结点记录三个信息，区间最长的连续空房间，最长前缀和后缀
//#pragma comment(linker, "/STACK:1024000000,1024000000") #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<iostream> #include<sstream> #include<cmath> #include<climits> #include<string> #include<map> #include<queue> #include<vector> #include<stack> #include<set> using namespace std; typedef long long ll; typedef pair<int,int> pii; #define pb(a) push_back(a) #define INF 0x1f1f1f1f #define lson idx<<1,l,mid #define rson idx<<1|1,mid+1,r #define PI 3.1415926535898 template<class T> T min(const T& a,const T& b,const T& c) { return min(min(a,b),min(a,c)); } template<class T> T max(const T& a,const T& b,const T& c) { return max(max(a,b),max(a,c)); } void debug() { #ifdef ONLINE_JUDGE #else freopen("d:\in.txt","r",stdin); freopen("d:\out1.txt","w",stdout); #endif } int getch() { int ch; while((ch=getchar())!=EOF) { if(ch!=' '&&ch!=' ')return ch; } return EOF; } const int MAXN=55000; struct node{ int maxv,pre,suf; }; node tree[MAXN<<2]; int setv[MAXN<<2]; int PushDown(int idx,int l,int r) { if(setv[idx]!=-1) { int mid=(r+l)>>1; setv[idx<<1]=setv[idx<<1|1]=setv[idx]; tree[idx<<1].maxv=tree[idx<<1].pre=tree[idx<<1].suf=setv[idx]*(mid-l+1); tree[idx<<1|1].maxv=tree[idx<<1|1].pre=tree[idx<<1|1].suf=setv[idx]*(r-mid); setv[idx]=-1; } return 0; } int PushUp(int idx,int l,int r) { int mid=(r+l)>>1; int ls=idx<<1,rs=idx<<1|1; tree[idx].maxv=max(tree[ls].maxv,tree[rs].maxv,tree[ls].suf+tree[rs].pre); tree[idx].pre=tree[ls].pre==mid-l+1?tree[ls].pre+tree[rs].pre:tree[ls].pre; tree[idx].suf=tree[rs].suf==r-mid?tree[rs].suf+tree[ls].suf:tree[rs].suf; return 0; } int build(int idx,int l,int r) { setv[idx]=-1; tree[idx].maxv=tree[idx].pre=tree[idx].suf=r-l+1; if(l==r)return 0; int mid=(r+l)>>1; build(lson); build(rson); return 0; } int update(int idx,int l,int r,int tl,int tr ,int v) { if(tl<=l&&tr>=r) { setv[idx]=v; tree[idx].maxv=tree[idx].pre=tree[idx].suf=v*(r-l+1); return 0; } PushDown(idx,l,r); int mid=(r+l)>>1; if(tl<=mid)update(lson,tl,tr,v); if(tr>mid)update(rson,tl,tr,v); PushUp(idx,l,r); return 0; } int query(int idx,int l,int r,int v){ if(r-l+1==v)return l; PushDown(idx,l,r); int mid=(r+l)>>1; if(tree[idx<<1].maxv>=v)return query(lson,v); else if(tree[idx<<1].suf!=0&&tree[idx<<1].suf+tree[idx<<1|1].pre>=v)return mid-tree[idx<<1].suf+1; else return query(rson,v); } int main(){ int n,m; while(scanf("%d%d",&n,&m)!=EOF) { build(1,1,n); for(int q=1;q<=m;q++) { int op; scanf("%d",&op); if(op==1){ int v; scanf("%d",&v); if(tree[1].maxv<v) printf("0 "); else { int pos=query(1,1,n,v); printf("%d ",pos); update(1,1,n,pos,pos+v-1,0); } }else { int a,b; scanf("%d%d",&a,&b);b=a+b-1; update(1,1,n,a,b,1); } } } return 0; }