|
|
Posted on 2012-05-04 20:05 C小加 阅读(1842) 评论(0) 编辑 收藏 引用 所属分类: 解题报告
区间合并的线段树题，也是我的第一个区间合并。 题意（转）：Bessie等牛到加拿大的桑德贝去增长文化修养外带观赏苏必利尔湖的阳光。按照导游的介绍，Bessie选择了著名的Cumberland大街上的Bullmoose宾馆作为居住的地点。 这座巨型宾馆在一条超长走廊上有N（1 ≤ N ≤ 50000）个排成一排的房间，每个房间都能欣赏到苏必利尔湖的好景色。现在所有的房间都是空的。 现在Bessie等旅客们正在不断地发出订房和退房要求。你需要接受M（1 ≤ M < 50000）条指令： 每条指令的第一个数字为1或2。如果是1，后面将有一个整数D表示顾客要预定的房间数。注意，这些房间必须是连续的。如果能够满足旅客的订房要求，输出满足要求的第一个房间的编号（例如，要订房6间，输出3表示3, 4, 5, 6, 7, 8是满足要求的），这样的编号必须是可能的编号里面最靠前的。如果不能满足要求，输出0。 如果是2，后面将有两个整数X和D表示顾客要退掉X, X + 1, X + 2, ... , X + D - 1这D间房。对于这样的指令什么都不输出。 分析： 分别用lsum，rsum和msum表示区间左边最大连续房间数，区间右边最大连续房间数和区间最大连续房间数。 查询的时候，先找左儿子是否足够，然后如果不够就找左儿子的右区间和右儿子的左区间的和是否足够，如果两个都不够的话就找右儿子（这个时候右儿子就肯定满足了）。 查询结束时要把这个区间的房子更新成已住。 更新的时候和普通的线段树节点更新是一样的，不同的是在更新完子节点后，要把子节点的信息反馈到父节点中。 在NYOJ中提交TLE，原因居然是宏定义比inline快。
#include<iostream> #include<cstring> #include<cctype> #include<cstdio> #include<algorithm> using namespace std; //没想到我把inline换成宏定义后就AC了，理论上这两个一样的，但是inline的结果却是TLE
#define L(r) r<<1 #define R(r) r<<1|1 //inline int MID(int l,int r){return (l+r)>>1;}
//inline int L(int r){return r<<1;}
//inline int R(int r){return r<<1|1;}
const int MAXM=50005; typedef struct{ int lsum,rsum,msum; //分别表示左边最大房间数，右边最大房间数，整体最大房间数
int cover; //是否住下
}node; node tree[MAXM<<2]; void pushDown( int root, int m) //向下更新
{ if(tree[root].cover==-1) return; //是否已经更新
tree[L(root)].cover=tree[R(root)].cover=tree[root].cover; tree[L(root)].msum=tree[L(root)].lsum=tree[L(root)].rsum=tree[root].cover?0:m-(m>>1); tree[R(root)].msum=tree[R(root)].lsum=tree[R(root)].rsum=tree[root].cover?0:(m>>1); tree[root].cover=-1; } void pushUp( int root, int m) //向上更新
{ tree[root].lsum=tree[L(root)].lsum; tree[root].rsum=tree[R(root)].rsum; if(tree[root].lsum==m-(m>>1) ) tree[root].lsum+=tree[R(root)].lsum; if(tree[root].rsum==(m>>1) ) tree[root].rsum+=tree[L(root)].rsum; tree[root].msum=max(tree[R(root)].lsum+tree[L(root)].rsum,max(tree[L(root)].msum,tree[R(root)].msum) ); } void Create( int l, int r, int root) //建树过程
{ tree[root].cover=-1; tree[root].lsum=tree[root].rsum=tree[root].msum=r-l+1; if(l==r){ return;} int mid=(l+r)>>1; Create(l,mid,L(root)); Create(mid+1,r,R(root)); } void update( int ll, int rr, int c, int l, int r, int root) //更新
{ if(ll<=l&&r<=rr) //如果找到这个范围就直接赋值返回，不向下继续更新
{ tree[root].msum=tree[root].lsum=tree[root].rsum=c?0:r-l+1; tree[root].cover=c; return; } pushDown(root,r-l+1); //用到这个节点的子节点的时候就向下更新
int m=(l+r)>>1; if(ll<=m) update(ll,rr,c,l,m,L(root)); if(m<rr) update(ll,rr,c,m+1,r,R(root)); pushUp(root,r-l+1); //向下更新完后需要把节点信息反馈给父节点
} int query( int w, int l, int r, int root) //查询满足连续房间数量的最左节点
{ if(l==r) return l; pushDown(root,r-l+1 ); //用到这个节点的子节点的时候就向下更新
int m=(l+r)>>1; if(tree[L(root)].msum>=w) return query(w,l,m,L(root)); //如果左儿子满足就询问左儿子
else if(tree[L(root)].rsum+tree[R(root)].lsum>=w) return m-tree[L(root)].rsum+1; //如果左儿子和右儿子之间的数量满足，则范围左儿子右边连续房间第一个的编号
return query(w,m+1,r,R(root)); //如果两者都不满足则询问右儿子
} int main() { //freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int n,m; while(~scanf("%d %d",&n,&m)) { Create(1,n,1); int a,num,x,d,p; for( int i=0;i<m;++i) { scanf("%d",&a); if(1==a) { scanf("%d",&num); if(tree[1].msum<num) puts("0"); //如果整个区间的最大连续房间数量小于预定的数量就输出0
else { p=query(num,1,n,1); //找到最左节点p
printf("%d\n",p); update(p,p+num-1,1,1,n,1); //把已经有人的房间标记一下
} } else { scanf("%d %d",&x,&d); update(x,x+d-1,0,1,n,1); //把此范围的房间标记成无人
} } } return 0; }
|