USACO08FEB Hotel

题目传送门

---

线段树维护区间

• 线段树结构体

struct zzz{
	int l,r,mi;
    //l为以左端点的为起点的最长子串
    //r为以右端点为终点的最长子串
    //mi是区间内部的最长子串
}tree[50010<<2];

• 合并
  合并的时候要考虑左右区间互拼的情况

inline void up(int l,int r,int p){
	if(tree[ls].l==mid-l+1)
	  tree[p].l=tree[ls].l+tree[rs].l;
	else tree[p].l=tree[ls].l;
	if(tree[rs].r==r-mid)
	  tree[p].r=tree[rs].r+tree[ls].r;
	else tree[p].r=tree[rs].r;
	tree[p].mi=max(max(tree[ls].mi,tree[rs].mi),tree[ls].r+tree[rs].l);
}

• 询问
  因为要查找最左的房间，所以尽量向左找

int query(int l,int r,int p,int k){
	down(l,r,p);
	if(l==r) return l;
	if(tree[ls].mi>=k) return query(l,mid,ls,k);
	if(tree[ls].r+tree[rs].l>=k) return mid-tree[ls].r+1;
	return query(mid+1,r,rs,k);
}

最核心的就是这几个函数了，别的函数基本没有变化，直接看总代码就好

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define ls p<<1
#define rs p<<1|1
#define mid ((l+r)>>1)
using namespace std;
int read(){
	int k=0,f=1; char c=getchar();
	for(;c<'0'||c>'9';c=getchar())
	  if(c=='-') f=-1;
	for(;c>='0'&&c<='9';c=getchar())
	  k=k*10+c-48;
	return k*f;
}
struct zzz{
	int l,r,mi;
}tree[50010<<2]; int tag[50010<<2];
inline void up(int l,int r,int p){
	if(tree[ls].l==mid-l+1)
	  tree[p].l=tree[ls].l+tree[rs].l;
	else tree[p].l=tree[ls].l;
	if(tree[rs].r==r-mid)
	  tree[p].r=tree[rs].r+tree[ls].r;
	else tree[p].r=tree[rs].r;
	tree[p].mi=max(max(tree[ls].mi,tree[rs].mi),tree[ls].r+tree[rs].l);
}
void build(int l,int r,int p){
	if(l==r){
		tree[p].l=tree[p].r=tree[p].mi=1;
		return ;
	}
	build(l,mid,ls); build(mid+1,r,rs);
	up(l,r,p);
}
inline void down(int l,int r,int p){
	if(tag[p]==-1) return ;
	tree[ls].l=tree[ls].mi=tree[ls].r=(mid-l+1)*tag[p];
	tree[rs].l=tree[rs].mi=tree[rs].r=(r-mid)*tag[p];
	tag[ls]=tag[rs]=tag[p];
	tag[p]=-1;
}
int query(int l,int r,int p,int k){
	down(l,r,p);
	if(l==r) return l;
	if(tree[ls].mi>=k) return query(l,mid,ls,k);
	if(tree[ls].r+tree[rs].l>=k) return mid-tree[ls].r+1;
	return query(mid+1,r,rs,k);
}
void update(int l,int r,int p,int nl,int nr,int k){
	if(l>=nl&&r<=nr){
		tree[p].l=tree[p].r=tree[p].mi=k*(r-l+1);
		tag[p]=k; return ;
	}
	down(l,r,p);
	if(nl<=mid) update(l,mid,ls,nl,nr,k);
	if(nr>mid) update(mid+1,r,rs,nl,nr,k);
	up(l,r,p);
}
int main(){
	int n=read(),m=read();
	memset(tag,-1,sizeof(tag));
	build(1,n,1);
	for(int i=1;i<=m;i++){
		int k=read();
		if(k==1){
			int x=read();
			if(tree[1].mi<x){
				printf("0
"); continue;
			}
			int pos=query(1,n,1,x);
			printf("%d
",pos);
			update(1,n,1,pos,pos+x-1,0);
		}
		else{
			int x=read(),y=read();
			update(1,n,1,x,x+y-1,1);
		}
	}
	return 0;
}