本文主要是介绍POJ 3667 Hotel ( 线段树区间合并 )，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接~~>
做题感悟：这题是接触线段树区间合并的第一题，做的很纠结。
解题思路：
注意线段树上节点代表的信息 ： 每个节点需要维护 lc , rc , mc ,add ,见下图：
add 为懒惰标记。假设 i 代表父亲节点编号，左儿子为 i * 2 ，右儿子为 i * 2 + 1 ,那么我们可以得到 ： T [ i ] .lc 首先加上左儿子的左边的空格数，然后需要判断一下，如果左儿子的左节点占满了整个左区间时需要再加上右儿子的左边的空格数。同理 T [ i ] .rc 也可以这样得到。那么 mc 怎样维护呢 ？ 无非是左儿子的 mc ,右儿子的 mc .不要忘记左儿子的右区间 + 右儿子的左区间也可以。这样就可以了。
代码：
#include<iostream>
#include<sstream>
#include<map>
#include<cmath>
#include<fstream>
#include<queue>
#include<vector>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<stack>
#include<bitset>
#include<ctime>
#include<string>
#include<cctype>
#include<iomanip>
#include<algorithm>
using namespace std ;
#define INT __int64
#define L(x) (x * 2)
#define R(x) (x * 2 + 1)
const int INF = 0x3f3f3f3f ;
const double esp = 0.0000000001 ;
const double PI = acos(-1.0) ;
const int mod = 1000000007 ;
const int MY = (1<<5) + 5 ;
const int MX = 50000 + 5 ;
const int S = 20 ;
int n ,m ;
struct node
{int le ,rt ,add ;int lc ,rc ,mc ;
}T[MX<<2] ;
void build(int i ,int le ,int rt) // 建树
{T[i].le = le ;T[i].rt = rt ;T[i].add = -1 ;T[i].lc = T[i].rc = T[i].mc = rt - le + 1 ;if(le == rt) return ;int Mid = (le + rt)>>1 ;build(L(i) ,le ,Mid) ;build(R(i) ,Mid+1 ,rt) ;
}
void push_down(int i) // 向下更新
{if(T[i].add != -1){int Mid = (T[i].rt + T[i].le)>>1 ;T[L(i)].add = T[R(i)].add = T[i].add ;T[L(i)].lc = T[L(i)].rc = T[L(i)].mc = T[i].add ? 0 : (Mid - T[i].le + 1) ;T[R(i)].lc = T[R(i)].rc = T[R(i)].mc = T[i].add ? 0 : (T[i].rt - Mid) ;T[i].add = -1 ;}
}
void push_up(int i) // 向上回溯
{T[i].lc = T[L(i)].lc ;T[i].rc = T[R(i)].rc ;if(T[L(i)].lc == T[L(i)].rt - T[L(i)].le + 1) //T[i].lc += T[R(i)].lc ;if(T[R(i)].rc == T[R(i)].rt - T[R(i)].le + 1)T[i].rc += T[L(i)].rc ;T[i].mc = max(max(T[L(i)].mc ,T[R(i)].mc) ,T[L(i)].rc + T[R(i)].lc) ;
}
void section(int i ,int le ,int rt ,int add) // 区间更新
{if(T[i].le == le && T[i].rt == rt){T[i].add = add ;T[i].lc = T[i].rc = T[i].mc = add ? 0 : (T[i].rt - T[i].le + 1) ;return ;}push_down(i) ;int Mid = (T[i].le + T[i].rt)>>1 ;if(le > Mid) section(R(i) ,le ,rt ,add) ;else if(rt <= Mid) section(L(i) ,le ,rt ,add) ;else{section(L(i) ,le ,Mid ,add) ;section(R(i) ,Mid+1 ,rt ,add) ;}push_up(i) ;
}
int Query(int i ,int Len) // 查询最左边的编号
{if(T[i].le == T[i].rt)return 1 ;push_down(i) ;int Mid = (T[i].le + T[i].rt)>>1 ;if(T[L(i)].mc >= Len) // 进入左区间return Query(L(i) ,Len) ;else if(T[L(i)].rc + T[R(i)].lc >= Len)return Mid - T[L(i)].rc + 1 ;elsereturn Query(R(i) ,Len) ;
}
int main()
{//freopen("input.txt" ,"r" ,stdin) ;int pos ,x ,L ;while(~scanf("%d%d" ,&n ,&m)){build(1 ,1 ,n) ;for(int i = 0 ;i < m ; ++i){scanf("%d" ,&pos) ;if(pos == 1){scanf("%d" ,&L) ; // 长度if(T[1].mc < L)puts("0") ;else{x = Query(1 ,L) ; // 查找最左边的编号printf("%d\n" ,x) ;section(1 ,x ,x+L-1 ,1) ; // 占满}}else{scanf("%d%d" ,&x ,&L) ; // 清空section(1 ,x ,x+L-1 ,0) ;}}}return 0 ;
}
这篇关于POJ 3667 Hotel ( 线段树区间合并 )的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
