PKU3667(Hotel)线段树
[cpp]
/**********************************************
题目大意:
有一个旅馆,有N个房间排成一排;
现在有两种操作:
第一是有a个顾客要入住连续的a个房间;
要求输出最小的左端点的位置,不能满足就输出0;
第二是将以a开始，长度为b的连续房间清空;
1 a: 询问是不是有连续长度为a的空房间,有的话住进最左边;
2 a b: 将[a,a+b-1]的房间清空;
算法思想:
记录区间中最长的空房间
lsum表示区间左边连续的空房个数;
rsum表示区间右边连续的空房个数;
msum表示区间上最大的一段空房的长度;
算法过程：
如果1~n区间的msum值都比x小，就无解，否则有解;
对于每一个区间，如果它的左儿子的msum值大于等于x,则到左儿子里去找;
如果左儿子的rsum加上右儿子的lsum大于等于x，则直接返回左儿子的右端点减去左儿子的rsum值;
否则到右儿子里去找;
***********************************************/
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<climits>
#include<algorithm>
using namespace std;
#define L l , m , u << 1
#define R m + 1 , r , u << 1 | 1
const int N = 55555;
int lsum[N<<2];//区间左边连续的空房个数;
int rsum[N<<2];//区间右边连续的空房个数;
int msum[N<<2];//区间上最大的一段空房的长度;
int cover[N<<2];
void PushDown(int u,int m)//把当前结点的信息更新给儿子结点
{
if (cover[u] != -1)
{
cover[u<<1] = cover[u<<1|1] = cover[u];
msum[u<<1] = lsum[u<<1] = rsum[u<<1] = cover[u] ? 0 : m - (m >> 1);
msum[u<<1|1] = lsum[u<<1|1] = rsum[u<<1|1] = cover[u] ? 0 : (m >> 1);
cover[u] = -1;
}
}
void PushUp(int u,int m)//把当前结点的信息更新到父结点
{
lsum[u] = lsum[u<<1];
rsum[u] = rsum[u<<1|1];
if(lsum[u] == m - (m >> 1))
lsum[u] += lsum[u<<1|1];
if(rsum[u] == (m >> 1))
rsum[u] += rsum[u<<1];
msum[u] = max(lsum[u<<1|1] + rsum[u<<1] , max(msum[u<<1] , msum[u<<1|1]));
}
void build(int l,int r,int u)
{
msum[u] = lsum[u] = rsum[u] = r - l + 1;
cover[u] = -1;
if (l == r)
return;
int m = (l + r) >> 1;
build(L);
build(R);
}
void update(int l1,int r1,int c,int l,int r,int u)//区间替换
{
if (l1 <= l && r <= r1)
{
msum[u] = lsum[u] = rsum[u] = c ? 0 : r - l + 1;
cover[u] = c;
return ;
}
PushDown(u , r - l + 1);
int m = (l + r) >> 1;
if (l1 <= m)
update(l1 , r1 , c , L);
if (m < r1)
update(l1 , r1 , c , R);
PushUp(u , r - l + 1);
}
int query(int w,int l,int r,int u)//查询满足条件的最左断点
{
if (l == r)
return l;
PushDown(u , r - l + 1);
int m = (l + r) >> 1;
if (msum[u<<1] >= w)//左儿子的msum值大于等于x,则到左儿子里去找;
return query(w , L);
else if (rsum[u<<1] + lsum[u<<1|1] >= w)//如果左儿子的rsum加上右儿子的lsum大于等于x，则直接返回左儿子的右端点减去左儿子的rsum值;
return m - rsum[u<<1] + 1;
return query(w , R);//否则到右儿子里去找;
}
int main()
{
//freopen("C:\\Users\\Administrator\\Desktop\\kd.txt","r",stdin);
int n , m;
scanf("%d%d",&n,&m);
build(1 , n , 1);
while (m--)
{
int op , a , b;
scanf("%d",&op);
if (op == 1)
{
scanf("%d",&a);
if (msum[1]<a)
puts("0");
else
{
int p = query(a , 1 , n , 1);
printf("%d\n",p);
update(p , p + a - 1 , 1 , 1 , n , 1);
} www.zzzyk.com
}
else
{
scanf("%d%d",&a,&b);
update(a , a + b - 1 , 0 , 1 , n , 1);
}
}
return 0;
}
补充：软件开发 , C++ ,
