记录编号	333898	评测结果	AAAAAAAAAA
题目名称	[HAOI 2013]软件安装	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.908 s
提交时间	2016-10-31 16:22:38	内存使用	3.34 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=50010;
void build(int,int,int);
void modify(int,int,int);
void query(int,int,int);
void pushdown(int,int,int,int);
void refresh(int,int,int,int);
int maxzero[maxn<<2],prefix[maxn<<2],suffix[maxn<<2],lazy[maxn<<2];
int n,m,pr,sm,x,s,t,d,ans;
int main(){
#define MINE
#ifdef MINE
	freopen("haoi13t4.in","r",stdin);
	freopen("haoi13t4.out","w",stdout);
#endif
	memset(lazy,-1,sizeof(lazy));
	scanf("%d%d",&n,&m);
	build(1,n,1);
	while(m--){
		scanf("%d",&d);
		if(d==1){
			scanf("%d",&x);
			if(maxzero[1]<x)printf("0\n");
			else{
				int L=x,R=n;
				while(L<=R){
					t=(L+R)>>1;
					//printf("L=%d R=%d M=%d\n",L,R,t);
					ans=pr=sm=0;
					query(1,n,1);//printf("ans=%d\n",ans);
					if(ans>=x)R=t-1;
					else L=t+1;
				}
				printf("%d\n",L-x+1);
				s=L-x+1;
				t=L;
				d=1;
				modify(1,n,1);
			}
		}
		else{
			scanf("%d%d",&s,&t);
			t+=s-1;
			d=0;
			modify(1,n,1);
		}
	}
#ifndef MINE
	printf("\n-------------------------DONE-------------------------\n");
	for(;;);
#else
	fclose(stdin);
	fclose(stdout);
#endif
	return 0;
}
void build(int l,int r,int rt){
	maxzero[rt]=prefix[rt]=suffix[rt]=r-l+1;
	if(l==r)return;
	int mid=(l+r)>>1;
	build(l,mid,rt<<1);
	build(mid+1,r,rt<<1|1);
}
void modify(int l,int r,int rt){
	if(s<=l&&t>=r){
		maxzero[rt]=prefix[rt]=suffix[rt]=((d)?(0):(r-l+1));
		lazy[rt]=d;
		return;
	}
	int mid=(l+r)>>1;
	pushdown(l,r,mid,rt);
	if(s<=mid)modify(l,mid,rt<<1);
	if(t>mid)modify(mid+1,r,rt<<1|1);
	refresh(l,r,mid,rt);
}
void query(int l,int r,int rt){
	if(t>=r){
		//printf("rt=%d pr=%d sm=%d\n",rt,pr,sm);
		ans=max(ans,maxzero[rt]);
		if(pr)ans=max(ans,suffix[pr]+prefix[rt]);
		ans=max(ans,sm+prefix[rt]);
		if(maxzero[rt]==r-l+1)sm+=r-l+1;
		else sm=suffix[rt];
		pr=rt;
		return;
	}
	int mid=(l+r)>>1;
	pushdown(l,r,mid,rt);
	query(l,mid,rt<<1);
	if(t>mid)query(mid+1,r,rt<<1|1);
}
void pushdown(int l,int r,int mid,int rt){
	if(lazy[rt]==-1)return;
	int lc=rt<<1,rc=lc|1;
	if(lazy[rt])maxzero[lc]=prefix[lc]=suffix[lc]=maxzero[rc]=prefix[rc]=suffix[rc]=0;
	else{
		maxzero[lc]=prefix[lc]=suffix[lc]=mid-l+1;
		maxzero[rc]=prefix[rc]=suffix[rc]=r-mid;
	}
	lazy[lc]=lazy[rc]=lazy[rt];
	lazy[rt]=-1;
}
void refresh(int l,int r,int mid,int rt){
	int lc=rt<<1,rc=lc|1;
	maxzero[rt]=max(suffix[lc]+prefix[rc],max(maxzero[lc],maxzero[rc]));
	if(maxzero[lc]==mid-l+1)prefix[rt]=mid-l+1+prefix[rc];
	else prefix[rt]=prefix[lc];
	if(maxzero[rc]==r-mid)suffix[rt]=r-mid+suffix[lc];
	else suffix[rt]=suffix[rc];
}
/*
10 6
1 3
1 3
1 3
1 3
2 5 5
1 6
Answer:
1
4
7
0
5
*/