P2894 [USACO08FEB]酒店Hotel

参考样例，第一行输入n，m ，n代表有n个房间，编号为1---n，开始都为空房，m表示以下有m行操作，以下 每行先输入一个数 i ，表示一种操作：

若i为1，表示查询房间，再输入一个数x，表示在1--n 房间中找到长度为x的连续空房，输出连续x个房间中左端的房间号，尽量让这个房间号最小，若找不到长度为x的连续空房，输出0。

若i为2，表示退房，再输入两个数 x，y 代表 房间号 x---x+y-1 退房，即让房间为空。

题目描述有坑啊。。。 一开始不知道操作一之后要区间覆盖为一，整的我tag只写了0的情况。。。

其实自己脑子有坑。。。 不覆盖为一这题还做啥。。。

头一次感觉自己代码写短了啊。。。

话说我的线段树结构体名字也成了SGT了。。吉利吉丽emmm

查询最左端的值，那么在查询的时候递归按照左中右的顺序找就可以了。

code：

#include <iostream>

#include <cstdio>

#define ls(o) o<<1

#define rs(o) o<<1|1

using namespace std;

const int wx=50017;

inline int read(){

	int sum=0,f=1; char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}

	while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-'0'; ch=getchar();}

	return sum*f;

}

int n,m;

struct SGT{

	int l,r,tag,lsum,rsum,sum;

	#define tag(o) t[o].tag

	#define lsum(o) t[o].lsum

	#define rsum(o) t[o].rsum

	#define sum(o) t[o].sum

}t[wx*4];

void up(int o){

	if(sum(ls(o))==t[ls(o)].r-t[ls(o)].l+1)lsum(o)=sum(ls(o))+lsum(rs(o));

	else lsum(o)=lsum(ls(o));

	if(sum(rs(o))==t[rs(o)].r-t[rs(o)].l+1)rsum(o)=sum(rs(o))+rsum(ls(o));

	else rsum(o)=rsum(rs(o));

	sum(o)=max(max(sum(ls(o)),sum(rs(o))),rsum(ls(o))+lsum(rs(o)));

}

void down(int o){

	if(tag(o)==0){

		sum(ls(o))=lsum(ls(o))=rsum(ls(o))=t[ls(o)].r-t[ls(o)].l+1;

		sum(rs(o))=lsum(rs(o))=rsum(rs(o))=t[rs(o)].r-t[rs(o)].l+1;

		tag(ls(o))=tag(rs(o))=tag(o);

		tag(o)=-1;

	}

	if(tag(o)==1){

		sum(ls(o))=lsum(ls(o))=rsum(ls(o))=0;

		sum(rs(o))=lsum(rs(o))=rsum(rs(o))=0;

		tag(ls(o))=tag(rs(o))=tag(o);

		tag(o)=-1;

	}

}

void build(int o,int l,int r){

	t[o].l=l; t[o].r=r; tag(o)=-1;

	if(l==r){sum(o)=lsum(o)=rsum(o)=1; return ;}

	int mid=t[o].l+t[o].r>>1;

	if(l<=mid)build(ls(o),l,mid);

	if(r>mid)build(rs(o),mid+1,r);

	up(o);

}

void update(int o,int l,int r,int k){

	if(l<=t[o].l&&t[o].r<=r){

		if(!k){

			sum(o)=lsum(o)=rsum(o)=t[o].r-t[o].l+1;

			tag(o)=k;

		}

		else{

			sum(o)=lsum(o)=rsum(o)=0;

			tag(o)=k;

		}

		return ;

	}

	down(o);

	int mid=t[o].l+t[o].r>>1;

	if(l<=mid)update(ls(o),l,r,k);

	if(r>mid)update(rs(o),l,r,k);

	up(o);

}

int query(int o,int l,int r,int len){

	if(l==r)return l;

	down(o);

	if(t[ls(o)].sum>=len)return query(ls(o),l,r,len);

	else if(t[ls(o)].rsum+t[rs(o)].lsum>=len)return t[ls(o)].r-rsum(ls(o))+1;

	else return query(rs(o),l,r,len);

}

int main(){

	n=read(); m=read(); build(1,1,n);

	for(int i=1;i<=m;i++){

		int opt;

		opt=read();

		if(opt==1){

			int x;

			x=read();

			if(sum(1)<x){

				puts("0");

				continue;

			}

			int tmp=query(1,1,n,x);

			printf("%d\n",tmp);

			update(1,tmp,tmp+x-1,1);

		}

		else{

			int x,y;

			x=read(); y=read();

			update(1,x,x+y-1,0);

		}

	}

	return 0;

}