UESTC 1227 & POJ 3667 Hotel

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <utility>
#include <cstdlib>
using namespace std;
#define N 80011struct node
{
int ls,rs,ms;
int pos;
int mark; // 0: unsure 1: all-empty 2: all-full
}tree[*N];int n,m;void build(int l,int r,int rt)
{
tree[rt].ls = tree[rt].rs = tree[rt].ms = r-l+;
tree[rt].pos = l;
if(l == r)
{
return;
}
int mid = (l+r)/;
build(l,mid,*rt);
build(mid+,r,*rt+);
}int if_all_empty(int l,int r,int rt)
{
if(tree[rt].ls == r-l+)
return ;
return ;
}void update(int l,int r,int rt)
{
if(!tree[rt].mark)
return;
if(tree[rt].mark == ) //全空，则下传给左右子树
{
int len = r-l+;
tree[*rt].ls = tree[*rt].rs = tree[*rt].ms = (len+)/;
tree[*rt].pos = l;
tree[*rt+].ls = tree[*rt+].rs = tree[*rt+].ms = len/;
tree[*rt+].pos = (l+r)/+;
tree[*rt].mark = tree[*rt+].mark = ;
}
else if(tree[rt].mark == ) //全满，则下传给左右子树
{
tree[*rt].ls = tree[*rt].rs = tree[*rt].ms = ;
tree[*rt].pos = l;
tree[*rt+].ls = tree[*rt+].rs = tree[*rt+].ms = ;
tree[*rt+].pos = (l+r)/+;
tree[*rt].mark = tree[*rt+].mark = ;
}
tree[rt].mark = ; // not "== 0"
}int query(int l,int r,int dis,int rt)
{
update(l,r,rt);
if(tree[rt].ms<dis)
return ;
if(tree[rt].ms == dis)
return tree[rt].pos;
int mid = (l+r)/;
if(tree[*rt].ms>=dis)
return query(l,mid,dis,*rt);
if(tree[*rt].rs + tree[*rt+].ls>=dis)
return mid - tree[*rt].rs + ;
return query(mid+,r,dis,*rt+);
}void in_out(int l,int r,int aa,int bb,int flag,int rt) //flag == 1: insert else quit
{
if(aa>r||bb<l)
return;
if(aa<=l&&bb>=r)
{
if(flag == ) //如果当前要入住
{
tree[rt].ls = tree[rt].rs = tree[rt].ms = ;
tree[rt].pos = l;
tree[rt].mark = ;
}
else //如果当前要退房
{
tree[rt].ls = tree[rt].rs = tree[rt].ms = r-l+;
tree[rt].pos = l;
tree[rt].mark = ;
}
return;
}
update(l,r,rt);
int mid = (l+r)/;
in_out(l,mid,aa,bb,flag,*rt);
in_out(mid+,r,aa,bb,flag,*rt+); tree[rt].ls = tree[*rt].ls;
if(if_all_empty(l,mid,*rt))
tree[rt].ls += tree[*rt+].ls;
tree[rt].rs = tree[*rt+].rs;
if(if_all_empty(mid+,r,*rt+))
tree[rt].rs += tree[*rt].rs; tree[rt].ms = max(tree[*rt].rs+tree[*rt+].ls,max(tree[*rt].ms,tree[*rt+].ms)); if(tree[rt].ms == tree[*rt].ms) //如果当前区间最大空房数等于左子树最大空房数
tree[rt].pos = tree[*rt].pos; //则起点置为左子树的起点 else if(tree[rt].ms == tree[*rt].rs + tree[*rt+].ls) //同理
tree[rt].pos = mid - tree[*rt].rs + ; else
tree[rt].pos = tree[*rt+].pos;
}int main()
{
scanf("%d%d",&n,&m);
memset(tree,,sizeof(tree));
build(,n,);
int i,flag;
int x,dis;
for(i=;i<m;i++)
{
scanf("%d",&flag);
if(flag == )
{
scanf("%d",&dis);
int ans = query(,n,dis,);
printf("%d\n",ans);
if(ans)
in_out(,n,ans,ans+dis-,,);
}
else if(flag == )
{
scanf("%d%d",&x,&dis);
in_out(,n,x,x+dis-,,);
}
}
return ;
}