POJ 3667 Hotel [线段树+区间更新]【数据结构】
题目链接:http://poj.org/problem?id=3667 ———————————————————————————. The cows are journeying north to Thunder Bay in Canada to gain cultural enrichment and enjoy a vacation on the sunny shores of Lake Superior. Bessie,ever the competent travel agent,has named the Bullmoose Hotel on famed Cumberland Street as their vacation residence. This immense hotel has N (1 ≤ N ≤ 50,000) rooms all located on the same side of an extremely long hallway (all the better to see the lake,of course). The cows and other visitors arrive in groups of size Di (1 ≤ Di ≤ N) and approach the front desk to check in. Each group i requests a set of Di contiguous rooms from Canmuu,the moose staffing the counter. He assigns them some set of consecutive room numbers r..r+Di-1 if they are available or,if no contiguous set of rooms is available,politely suggests alternate lodging. Canmuu always chooses the value of r to be the smallest possible. Visitors also depart the hotel from groups of contiguous rooms. Checkout i has the parameters Xi and Di which specify the vacating of rooms Xi ..Xi +Di-1 (1 ≤ Xi ≤ N-Di+1). Some (or all) of those rooms might be empty before the checkout. Your job is to assist Canmuu by processing M (1 ≤ M < 50,000) checkin/checkout requests. The hotel is initially unoccupied. Input
Output
Sample Input 10 6 1 USACO 2008 February Gold 题目大意: 解题思路: 思路构建的很容易,但是最后代码实现的时候发现好麻烦啊,因为一个rr写成了ll 硬是调试了2个小时有没有啊…….. 跟普通的区间更新差别也就是在pushup和pushdown两个操作上面. /* 维护左右的最大值,在维护区间内的最大值就好了 */
void pushup(int rt){
if(tree[ll].ls == tree[ll].len())
tree[rt].ls = tree[ll].len() + tree[rr].ls;
else tree[rt].ls = tree[ll].ls;
if(tree[rr].rs == tree[rr].len())
tree[rt].rs = tree[rr].len() + tree[ll].rs;
else tree[rt].rs = tree[rr].rs;
tree[rt].val = max(tree[ll].rs + tree[rr].ls,max(tree[rr].val,tree[ll].val));
}
pushdown /* 这时候 0代表入房 1代表退房 维护的时候直接tree[ll].len()*tree[rt].lazy;就好了 方便 代码还短一点. */
void pushdown(int rt){
if(tree[rt].lazy != -1){
tree[ll].lazy = tree[rr].lazy = tree[rt].lazy;
tree[ll].val = tree[ll].ls = tree[ll].rs = tree[ll].len()*tree[rt].lazy;
tree[rr].val = tree[rr].ls = tree[rr].rs = tree[rr].len()*tree[rt].lazy;
tree[rt].val = tree[rt].ls = tree[rt].rs = tree[rt].len()*tree[rt].lazy;
tree[rt].lazy = -1;
}
}
附本题代码 //#include <bits/stdc++.h>
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <vector>
#include <map>
#include <queue>
using namespace std;
#define INF (~(1<<31))
#define INFLL (~(1ll<<63))
#define pb push_back
#define mp make_pair
#define abs(a) ((a)>0?(a):-(a))
#define lalal puts("*******");
#define s1(x) scanf("%d",&x)
#define Rep(a,b,c) for(int a=(b);a<=(c);a++)
#define Per(a,c) for(int a=(b);a>=(c);a--)
#define no puts("NO")
typedef long long int LL ;
typedef unsigned long long int uLL ;
const int MOD = 1e9+7;
const int N = 50000+5;
const double eps = 1e-6;
const double PI = acos(-1.0);
/***********************************************************************/
struct node {
int l,r;
int val;
int ls,rs;
int lazy;
int md(){return (l+r)>>1;}
int len(){return (r-l+1);}
}tree[N<<2];
#define ll (rt<<1)
#define rr (rt<<1|1)
#define mid (tree[rt].md())
void pushup(int rt){
if(tree[ll].ls == tree[ll].len())
tree[rt].ls = tree[ll].len() + tree[rr].ls;
else tree[rt].ls = tree[ll].ls;
if(tree[rr].rs == tree[rr].len())
tree[rt].rs = tree[rr].len() + tree[ll].rs;
else tree[rt].rs = tree[rr].rs;
tree[rt].val = max(tree[ll].rs + tree[rr].ls,max(tree[rr].val,tree[ll].val));
}
void build(int rt,int l,int r){
tree[rt].l =l,tree[rt].r=r,tree[rt].lazy=-1;
tree[rt].val=tree[rt].ls=tree[rt].rs=tree[rt].len();
if(l==r) return ;
build(ll,l,mid);
build(rr,mid+1,r);
}
void pushdown(int rt){
if(tree[rt].lazy != -1){
tree[ll].lazy = tree[rr].lazy = tree[rt].lazy;
tree[ll].val = tree[ll].ls = tree[ll].rs = tree[ll].len()*tree[rt].lazy;
tree[rr].val = tree[rr].ls = tree[rr].rs = tree[rr].len()*tree[rt].lazy;
tree[rt].val = tree[rt].ls = tree[rt].rs = tree[rt].len()*tree[rt].lazy;
tree[rt].lazy = -1;
}
}
void update(int rt,int L,int R,int op){ //update 就是将 所有的 [a,a+b-1] 清一下
if(L<=tree[rt].l&&tree[rt].r<=R){
if(1 == op){ //入住
tree[rt].val = tree[rt].ls = tree[rt].rs = 0;
tree[rt].lazy = 0;
}
else { //退房
tree[rt].val = tree[rt].ls = tree[rt].rs = tree[rt].len();
tree[rt].lazy = 1;
}
return ;
}
pushdown(rt);
if(L<=mid) update(ll,L,R,op);
if(R> mid) update(rr,op);
pushup(rt);
}
int query(int rt,int val){
if(tree[rt].l==tree[rt].r){
if(val == tree[rt].val) return tree[rt].l;
return 0;
}
pushdown(rt);
if(tree[ll].val>=val)
return query(ll,val);
else if(tree[rr].ls+tree[ll].rs >= val)
return tree[ll].r-tree[ll].rs+1;
else if(tree[rr].val >= val)
return query(rr,val);
return 0;
}
int main()
{
int n,m;
int op,a,b;
while(~s1(n)){
s1(m);
build(1,1,n);
Rep(i,m){
s1(op);
if(1==op){
s1(a);
int tem = query(1,a);
if(tem) update(1,tem,a+tem-1,op);
printf("%dn",tem);
}
else {
s1(a),s1(b);
update(1,a+b-1,op);
}
}
}
return 0;
}
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |