USACO08FEB Hotel G

题目描述

分析

可以用线段树维护区间内连续的空房的最长长度，但转念一想，连续的空房可以横跨左孩子管辖的区间和右孩子管辖的区间，所以还得维护从区间开头开始的最长连续空房，和从区间结尾开始的最长连续空房，更新节点信息的代码：

void push_up(int cur, int l, int r){
	int mid = (l + r) / 2;
	tree[cur].ls = tree[cur * 2].ls;//从区间开头开始的最长连续空房为他左孩子的答案
	if(tree[cur * 2].ls == mid - l + 1){//如果他左孩子的答案是整个区间则还可以跟右孩子的答案拼一起
		tree[cur].ls = tree[cur * 2].ls + tree[cur * 2 + 1].ls; 
	} 
	tree[cur].rs = tree[cur * 2 + 1].rs;//同理
	if(tree[cur * 2 + 1].rs == r - mid){
		tree[cur].rs = tree[cur * 2].rs + tree[cur * 2 + 1].rs;
	}
	tree[cur].ans = max(tree[cur * 2].ans, tree[cur * 2 + 1].ans);//连续的空房的最长长度为左孩子的答案和右孩子的答案的最大值
	tree[cur].ans = max(tree[cur].ans, tree[cur * 2].rs + tree[cur * 2 + 1].ls);//左孩子从结尾开始的空房还可以跟右孩子从开头开始的空房拼一起
}

而查询时如果左边的区间满足答案，则返回左边的，如果中间的满足答案，则返回中间的，否则返回后面的。

int query(int cur, int l, int r, int val){
	if(l == r){//找到答案
		return l;
	}
	push_down(cur, l, r);//懒标记下传
	int mid = (l + r) / 2;
	if(tree[cur * 2].ans >= val){
		return query(cur * 2, l, mid, val);
	}if(tree[cur * 2].rs + tree[cur * 2 + 1].ls >= val){
		return mid - tree[cur * 2].rs + 1;
	}
	return query(cur * 2 + 1, mid + 1, r, val);
}

修改、标记下传、和建树都很简单，代码如下：

void push_down(int cur, int l, int r){
	if(!tag[cur]){//没标记不下传
		return ;
	}
	if(tag[cur] == 1){//l到r全住人
		tag[cur * 2] = tag[cur * 2 + 1] = 1;
		tree[cur * 2].ans = tree[cur * 2].ls = tree[cur * 2].rs = 0;
		tree[cur * 2 + 1].ans = tree[cur * 2 + 1].ls = tree[cur * 2 + 1].rs = 0;
	}else{//l到r退房
		int mid = (l + r) / 2;
		tag[cur * 2] = tag[cur * 2 + 1] = 2;
		tree[cur * 2].ans = tree[cur * 2].ls = tree[cur * 2].rs = mid - l + 1;
		tree[cur * 2 + 1].ans = tree[cur * 2 + 1].ls = tree[cur * 2 + 1].rs = r - mid;
	}
	tag[cur] = 0;
}
void build(int cur, int l, int r){
	if(l == r){
		tree[cur].ans = tree[cur].ls = tree[cur].rs = 1;
		return ;
	}
	int mid = (l + r) / 2;
	build(cur * 2, l, mid);
	build(cur * 2 + 1, mid + 1, r);
	push_up(cur, l, r);
}
void update(int cur, int l, int r, int qx, int qy, int val){
	if(qx > r || qy < l){//当前区间完全不包含
		return ;
	}if(qx <= l && r <= qy){//完全包含
		tag[cur] = val;
		if(val == 1){
			tree[cur].ans = tree[cur].ls = tree[cur].rs = 0; 
		}else if(val == 2){
			tree[cur].ans = tree[cur].ls = tree[cur].rs = r - l + 1;
		}
		return ;
	}
	push_down(cur, l, r);
	int mid = (l + r) / 2;//只包含一部分就继续递归
	update(cur * 2, l, mid, qx, qy, val);
	update(cur * 2 + 1, mid + 1, r, qx, qy, val);
	push_up(cur, l, r);
}

主函数：

int main(){
	cin >> n >> m;
	build(1, 1, n);
	while(m --){
		int Type, x, y;
		cin >> Type;
		if(Type == 1){
			cin >> x;
			if(tree[1].ans >= x){
				int now = query(1, 1, n, x);
				cout << now << "\n";
				update(1, 1, n, now, now + x - 1, 1);
			}else{//如果1到n的区间都不满足答案就无解
				cout << "0\n";
			}
		}else{
			cin >> x >> y;
			update(1, 1, n, x, x + y - 1, 2);
		}
	}
	return 0;
}

完整代码自己拼接吧……