USACO08FEB Hotel G

2023-12-29 01:12

文章标签 hotel usaco08feb

本文主要是介绍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;
}