首页 > 代码库 > PKU 3667 Hotel (线段树,区间合并,最长连续区间)

PKU 3667 Hotel (线段树,区间合并,最长连续区间)



题意:宾馆有N个房间(1~N),M个操作,a=1,输入b,表示N间房是否有连续的b间房。有输出最左边的房编号


没有输出0。a=2,输入b,c表示房间b到c清空。


模仿了大神的代码,敲了一遍,有些地方还要深入了解。技术分享


#include <stdio.h>  
#include <iostream>  
#include <algorithm>  
#include <string.h>  
#include <queue> 
#include <math.h>  
#define M 50001  
#define eps 1e-6
#define LL long long  
using namespace std;

struct node
{
	int left,right;
	int lsum,rsum,msum;
	int lazy;
}tree[M*3];

void push_up(int id)
{
	int ll=tree[id<<1].right-tree[id<<1].left+1;
	int rr=tree[id<<1|1].right-tree[id<<1|1].left+1;
	tree[id].lsum=tree[id<<1].lsum;
	if(tree[id<<1].lsum==ll) 
		tree[id].lsum+=tree[id<<1|1].lsum;
	tree[id].rsum=tree[id<<1|1].rsum;
	if(tree[id].rsum==rr)
		tree[id].rsum+=tree[id<<1].rsum;
	tree[id].msum = max(max(tree[id<<1].msum,tree[id<<1|1].msum),tree[id<<1].rsum+tree[id<<1|1].lsum);
}
void push_down(int id)
{
	if(tree[id].lazy!=-1)
	{
		int ll=tree[id<<1].right-tree[id<<1].left+1;
		int rr=tree[id<<1|1].right-tree[id<<1|1].left+1;
		tree[id<<1].lazy=tree[id<<1|1].lazy=tree[id].lazy;
		tree[id].lazy=-1;
		tree[id<<1].rsum = tree[id<<1].lsum = tree[id<<1].msum = tree[id<<1].lazy ?

0:ll; tree[id<<1|1].rsum = tree[id<<1|1].lsum = tree[id<<1|1].msum = tree[id<<1|1].lazy ?0:rr; } } void build(int id,int l,int r) { tree[id].left=l;tree[id].right=r; tree[id].lsum=tree[id].rsum=tree[id].msum=(r-l+1); tree[id].lazy=-1; if(l==r) return ; int mid=(l+r)/2; build(id<<1,l,mid); build(id<<1|1,mid+1,r); //push_up(id); } void update(int id,int l,int r,int c) { if(tree[id].left==l&&tree[id].right==r) { tree[id].lsum=tree[id].rsum=tree[id].msum=c?0:(r-l+1); tree[id].lazy=c; return ; } push_down(id); int mid=(tree[id].left+tree[id].right)/2; if(r<=mid) update(id<<1,l,r,c); else if(l>mid) update(id<<1|1,l,r,c); else { update(id<<1,l,mid,c); update(id<<1|1,mid+1,r,c); } push_up(id); } int query(int id,int v) { if(tree[id].left==tree[id].right) return tree[id].left; push_down(id); int mid=(tree[id].left+tree[id].right)/2; if(tree[id<<1].msum>=v)//假设左子树的最大连续空>=需求量。那么直接进入左子树,=也去左子树的原因是题目要求的最左 return query(id<<1,v); else if(tree[id<<1].rsum+tree[id<<1|1].lsum>=v)//左子树的连续右+右子树的连续左>=w,说明找到了能够直接求出 return mid-tree[id<<1].rsum+1; return query(id<<1|1,v); } int main() { int n,m; while(~scanf("%d%d",&n,&m)) { int a,b,c; build(1,1,n); while(m--) { scanf("%d",&a); if(a==1) { scanf("%d",&c); if(tree[1].msum<c) printf("0\n");//根节点的最大连续空间不够 else { int p=query(1,c); printf("%d\n",p); update(1,p,p+c-1,1);//把这段更新为被覆盖 } } else { scanf("%d%d",&b,&c); update(1,b,b+c-1,0);//把这段更新为未被覆盖 } } } return 0; } /* 10 6 1 3 1 3 1 3 1 3 2 5 5 1 6 */



PKU 3667 Hotel (线段树,区间合并,最长连续区间)