1. 首页
2. 线段树
3. 本页

Poj 3667 Hotel (线段树区间合并)

题意:1 a:询问是不是有连续长度为 a 的空房间,有的话住进最左边
2 a b:将[a,a+b-1]的房间清空
思路:记录区间中最长的空房间
线段树操作:update:区间替换 query:询问满足条件的最左断点

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
using namespace std;

#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

const int MAXN = 50010;

int msum[MAXN << 2];
int lsum[MAXN << 2];    //从左开始的最大连续可用区间
int rsum[MAXN << 2];   //从右开始的最大连续可用区间
int col[MAXN << 2];

void pushup(int rt, int ans) {
	lsum[rt] = lsum[rt << 1];
	rsum[rt] = rsum[rt << 1 | 1];
	if (lsum[rt] == ans - (ans >> 1)) {     //如果这一段达到最大 需要加上相邻的另一半 
		lsum[rt] += lsum[rt << 1 | 1];       //从左往右加
	}
	if (rsum[rt] == (ans >> 1)) {
		rsum[rt] += rsum[rt << 1];            //从右往左加
	}
	//当前区间的tlen = max{ 左半区间tlen , 右半区间tlen , 左半区间rlen+右半区间llen} 
	//      取左右较大的那个，或者横跨中间的那个
	msum[rt] = max(max(msum[rt << 1], msum[rt << 1 | 1]),
			lsum[rt << 1 | 1] + rsum[rt << 1]);
}

void pushdown(int rt, int ans) {
	if (col[rt] != -1) {    // 1表示已经覆盖   0表示初始化
		col[rt << 1] = col[rt << 1 | 1] = col[rt];
		msum[rt << 1] = lsum[rt << 1] = rsum[rt << 1] =
				col[rt] ? 0 : ans - (ans >> 1);
		msum[rt << 1 | 1] = lsum[rt << 1 | 1] = rsum[rt << 1 | 1] =
				col[rt] ? 0 : (ans >> 1);
		col[rt] = -1;
	}
}

void build(int l, int r, int rt) {
	msum[rt] = lsum[rt] = rsum[rt] = r - l + 1;
	col[rt] = -1;
	if (l == r) {
		return;
	}
	int m = (l + r) >> 1;
	build(lson);
	build(rson);
}

void update(int L, int R, int c, int l, int r, int rt) {
	if (L <= l && r <= R) {
		msum[rt] = lsum[rt] = rsum[rt] = c ? 0 : (r - l + 1);
		col[rt] = c;
		return;
	}
	pushdown(rt, r - l + 1);
	int m = (l + r) >> 1;
	if (L <= m) {
		update(L, R, c, lson);
	}
	if (R > m) {
		update(L, R, c, rson);
	}
	pushup(rt, r - l + 1);
}

int query(int res, int l, int r, int rt) {
	if (l == r) {
		return l;     //返回下标
	}
	pushdown(rt, r - l + 1);
	int m = (l + r) >> 1;
	if (msum[rt << 1] >= res) {     //左孩子区间满足 
		return query(res, lson);
	} else if ((lsum[rt << 1 | 1] + rsum[rt << 1]) >= res) {    //横跨区间满足 直接返回下标
		return m - rsum[rt << 1] + 1;
	}
	return query(res, rson);
}

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	build(1, n, 1);
	int op, a, b;
	while (m--) {
		scanf("%d", &op);
		if (op == 1) {
			scanf("%d", &a);
			if (msum[1] < a) {
				puts("0");
			} else {              //查询完区间情况 要更新进去
				int q = query(a, 1, n, 1);
				printf("%d\n", q);
				update(q, q + a - 1, 1, 1, n, 1);
			}
		} else {
			scanf("%d%d", &a, &b);
			update(a, a + b - 1, 0, 1, n, 1);
		}
	}

	return 0;
}

来自某位大婶的感悟：用线段树，首先要定义好线段树的节点信息，一般看到一个问题，很难很快能确定线段树要记录的信息
做线段树不能为了做题而做，首先线段树是一种辅助结构，它是为问题而生的，因而必须具体问题具体分析
回忆一下RMQ问题，其实解决RMQ有很多方法，根本不需要用到线段树，用线段树解决RMQ，其实是利用线段树的性质来辅助解决这个问题
回忆一下求矩形面积并或周长并的问题，一般使用的是扫描线法，其实扫描线法和线段树一点关系都没有，扫描线法应该归为计算几何的算法，
使用线段树只是为了辅助实现扫描线法

因而回到这题，要解，必须分析问题本质，才去思考怎么用线段树来辅助，另外为什么能用线段树辅助是可行的，这个问题似乎更有价值

1 查询操作，找一段长度为W的没被覆盖的最左的区间
2 更新操作，将某段连续的区域清空

更新操作相对容易解决，关键是怎么实现查询操作
既然是要找一段长度至少为W的区间，要做到这点，其实不难，我们可以在每个线段树的节点里增加一个域tlen，表示该区间可用的区间的最大长度，
至于这个tlen区间的具体位置在哪里不知道，只是知道该区间内存在这么一段可用的区间，并且注意，这个tlen表示的是最大长度，该节点可能有多段可用的区间，但是最长的长度是tlen
记录了这个信息，至少能解决一个问题，就是能不能找到一个合适的区间。如果查询的区间长度W > 总区间的tlen，那么查询一定是失败的（总区间中可以的最大区间都不能满足那就肯定失败）
但这远远不够，其一查询是要返回区间的具体位置的，这里无法返回位置，另外是要查询最左区间，最左的且满足>=W的区间可能不是这个tlen区间

那么我们进一步思考这个问题
首先我们先增加两个域,llen,rlen
llen表示一个区间从最左端开始可用的且连续的最大长度
例如区间[1,5]，覆盖情况为[0,0,0,1,1]，llen = 3，从最左端有3格可以利用
区间[1,5]，覆盖情况为[1,0,0,0,0]，llen = 0，因为从最左端开始找不到1格可用的区间
rlen表示一个区间从最右端开始可用的且连续的最大长度
例如区间[1,5]，覆盖情况为[1,0,1,0,0]，rlen = 2，从最右端有2格可以利用
区间[1,5]，覆盖情况为[0,0,0,0,1]，rlen = 0，因为从最右端开始找不到1格可用的区间
对于一个区间，我们知道它左半区间的tlen，和右半区间的tlen，如果左半区间的tlen >= W ,那么我们一定能在左边找到（满足最左），所以可以深入到左半区间去确定该区间的具体位置
如果左端的不满足，那么我们要先考虑横跨两边的区间（因为要满足最左），因而记录的llen,rlen可以派上用场，一段横跨的区间，
那么是 左边区间rrlen + 右边区间llen ，如果满足的话，就是该区间了，它的位置也是可以确定的
如果横跨的区间不满足，那么就在右半区间找，如果右半区间的tlen >= W , 那么可以在右半区间找到，所以深入到右半区间去确定它的具体位置，否则的话，整个查询就失败了

可见查询是建立在tlen,llen,rlen这个信息之上的，而每次查询后其实伴随着修改，而且还有专门的修改操作，这些修改操作都会改变tlen,llen,rlen的值，所以在更新的时候是时刻维护这些信息

关于这3个信息的维护

当前区间的tlen = max{ 左半区间tlen , 右半区间tlen , 左半区间rlen+右半区间llen} （这个不难理解吧，取左右较大的那个，或者横跨中间的那个）

如果左半区间全部可以用: 当前区间llen = 左半区间llen(tlen) + 右半区间llen
左半区间部分能用: 当前区间llen = 左半区间llen

如果右半区间全部能用: 当前区间rlen = 右半区间rlen(tlen) + 左半区间rlen
右半区间部分能用: 当前区间rlen = 右半区间rlen

这样就全部维护好了