首页 > 代码库 > TreeSegment1823
TreeSegment1823
题意：一个hotel，有n间连续的房间，现在有m组操作：
type 1: ‘1, a, b‘: 第a个房间起的b个房间有旅客入住。
type 2: ‘2, a, b‘: 第a个房间起的b个房间的旅客离开。
type 3: ‘3‘: 问最长的连续空房间有多少间。
这样的问题一般都是问你区间中满足条件最长的序列，你关键需要知道怎样操作对线段树左右儿子进行合并。
这样的问题一般都要定义三个数组lm（定义从区间左边第一个点开始的满足条件的序列）， rm（定义以区间右边最后一个点结束的满足条件的序列）， sm（定义整个区间满足条件的最长序列）。
#include<iostream>
using namespace std;
const int Max = 30;
struct{
int l, r;
int lma, ma, rma; // lma为这个区间左边的最长连续空房间的数量。//lma左连续的人数，rma右连续的人数，len 是node[u]的最大连续人数
int cover; //‘1’表示这个区间的房间全住人，‘-1’表示全空，‘0’表示有空用住。
}node[3*Max];
int max(int a, int b){
return a > b ? a : b;
}
void BuildTree(int left, int right, int u){ // 建树。
node[u].l = left;
node[u].r = right;
if(left == right) return;
int mid = (left + right)>>1;
BuildTree(left, mid, u<<1);
BuildTree(mid+1, right, (u<<1)+1);///这里线段树不是用来表示线段，而是节点，因此不能出现[1,2][2,3]
}
void getdown(int u, int op){
node[u].cover = 0;
/*走到这里的时候，说明不能完全匹配。根节点初始化为-1，即原先所有房子都是空的，因此第一次遇到的时候。
原先实参OP=1（表示有人进入房子），这里的形参OP=-1,首先令左半段和右半段全部为空（初始化时并没有赋值）。
在后面的UPDATA中，如果找到完全匹配，那么就不用进入getdown中，否则不能匹配则首先令两个子节点状态和父节点
一模一样.PUSHDOWN意义在于由于线段树根节点满足条件时，子节点就不用更新了（但是子节点的信息是错误信息），那么下次要用到子节点到时候（即根节点不能完全匹配的时候），再把根节点的状态给两个子节点。*/
node[u<<1].cover = op;
node[(u<<1)+1].cover = op;
if(op == 1){//由空房间变成满房间
node[u<<1].lma = 0;
node[u<<1].ma = 0;
node[u<<1].rma = 0;
node[(u<<1)+1].lma = 0;
node[(u<<1)+1].ma = 0;
node[(u<<1)+1].rma = 0;
}
else{
int len;
len = node[u<<1].r - node[u<<1].l + 1;
node[u<<1].lma = len;
node[u<<1].ma = len;
node[u<<1].rma = len;
len = node[(u<<1)+1].r - node[(u<<1)+1].l + 1;
node[(u<<1)+1].lma = len;
node[(u<<1)+1].ma = len;
node[(u<<1)+1].rma = len;
}
}
void updata(int left, int right, int op, int u)
{ // 修改。
if(left <= node[u].l && right >= node[u].r)//完全匹配最好处理，修改好所有数据后 退出
{
node[u].cover = op;
if(op == 1)//如果住人，那么空房间连续区间都是0
node[u].lma = node[u].ma = node[u].rma = 0;
else//整个区间都是空，那么无论左边 右边的连续空区间长度都是区间长度
{
int len = node[u].r - node[u].l + 1;
node[u].lma = node[u].ma = node[u].rma = len;
}
return;//已经找到 就直接return
}
if(node[u].cover == op)
return;//该区域没有合适的了，大的都不够用，往下小的区域更不够
if(node[u].cover == -op)
getdown(u, -op);
/*注意是-op，该句只会在1变成-1，或者-1变成1才会使用，走到这里的时候，说明不能完全匹配*/
if(right <= node[u<<1].r)
updata(left, right, op, u<<1);
else if(left >= node[(u<<1)+1].l)
updata(left, right, op, (u<<1)+1);
else
{
updata(left, right, op, u<<1);//right没有写成node[u<<1].r所以判断条件是left <= node[u].l && right >= node[u].r而不是用等于号
updata(left, right, op, (u<<1)+1);
}
// *所有递归结束以后才返回到这里，即递归到最深的子节点以后再逐步修改push_up到父节点，由左右子结点的信息，对父结点的三个连续区间最大值进行相应的更改。
if(node[u<<1].cover == -1) // 求父结点的lma。
node[u].lma = node[u<<1].ma + node[(u<<1)+1].lma;
else
node[u].lma = node[u<<1].lma;
if(node[(u<<1)+1].cover == -1) // 求父结点的rma。
node[u].rma = node[(u<<1)+1].ma + node[u<<1].rma;
else
node[u].rma = node[(u<<1)+1].rma;
// 求父结点的ma:
int a = node[u<<1].rma + node[(u<<1)+1].lma;//a,b,c分别对应5种情况，取最大的那个。1左孩子右边与右孩子左边连续的空间
int b = max(node[u<<1].ma, node[(u<<1)+1].ma);//2左孩子自身的连续，3右孩子自身的连续
int c = max(node[u].lma, node[u].rma);//4左孩子左边自身的连续，5,右孩子右边自身的连续
node[u].ma = max(max(a, b), c);
// *递归回来的时候，由于左右子结点性质的改变，必须对父结点信息进行相应的更改，WA在了这里。
if(node[u<<1].cover == node[(u<<1)+1].cover)
node[u].cover = node[u<<1].cover;
}
int main(){
int n, m;
scanf("%d%d", &n, &m);
BuildTree(1, n, 1);
node[1].cover = -1; //初始时根节点全空，空房间数量为n
node[1].ma = n;
while(m --)
{
int op, a, b;
scanf("%d", &op);
if(op == 1)
{
scanf("%d%d", &a, &b);
updata(a, a+b-1, 1, 1); // 为a+b-1，不能算成a+b。
}
else if(op == 2){
scanf("%d%d", &a, &b);
updata(a, a+b-1, -1, 1);
}
else
printf("%d\n", node[1].ma);
}
return 0;
}
TreeSegment1823