线段树【洛谷P2894】 [USACO08FEB]酒店Hotel

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
",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;
}