题目描述
To earn some extra money, the cows have opened a restaurant in their barn specializing in milkshakes. The restaurant has N seats )
in a row. Initially, they are all empty.
Throughout the day, there are M different events that happen in sequence at the restaurant )
. The two types of events that can happen are:
1. A party of size p arrives )
. Bessie wants to seat the party in a contiguous block of p empty seats. If this is possible, she does so in the lowest position possible in the list of seats. If it is impossible, the party is turned away.
2. A range [a,b] is given )
, and everybody in that range of seats leaves. Please help Bessie count the total number of parties that are turned away over the course of the day.
输入描述:
* Line 1: Two space-separated integers,and
.
* Lines 2..M+1: Each line describes a single event. It is either aline of the form "A p" (meaning a party of size p arrives) or"L a b" (meaning that all cows in the rangeleave).
输出描述:
* Line 1: The number of parties that are turned away.
示例1
输入
10 4
A 6
L 2 4
A 5
A 2
输出
1
说明
INPUT DETAILS:
There are 10 seats, and 4 events. First, a party of 6 cows arrives. Then
all cows in seats 2..4 depart. Next, a party of 5 arrives, followed by a
party of 2.
OUTPUT DETAILS:
Party #3 is turned away. All other parties are seated.
解答
想起大一的时候小学期做过同样的题目，不过那个时候得到数据规模是很小的，所以当时的我是暴力做的。
拿到这个题，第一个想到线段树，去记录区间可用的seat有多少个。这么做还不够，还需要能找到安排时最左的满足条件的坐标。
那线段树就需要再多记录两个元素。一个是从左往右数空闲位置的个数，另一个是从右往左树空闲位置的个数。
说的再多，也不如代码清楚：
来源：Bing_Bodybuilding
拿到这个题，第一个想到线段树，去记录区间可用的seat有多少个。这么做还不够，还需要能找到安排时最左的满足条件的坐标。
那线段树就需要再多记录两个元素。一个是从左往右数空闲位置的个数，另一个是从右往左树空闲位置的个数。
说的再多，也不如代码清楚：
#include<bits/stdc++.h>
using namespace std;
const int maxn = 500000 + 10;
// static const int maxn = 15;
const int REMOVE_ALL = 1;
const int PLACE = 2;
const int mi = maxn*3;
class Node {
public:
int numFromLeft;
int numFromRight;
int value;
int lazyType;
Node(int numFromLeft, int numFromRight, int value, int lazyType) {
this->numFromLeft = numFromLeft;
this->numFromRight = numFromRight;
this->value = value;
this->lazyType = lazyType;
}
Node() {}
};
Node nodes[maxn * 4];
// static {
// for (int i = 0; i < nodes.length; ++i)
// nodes[i] = new Node();
// }
void updateLeftRight(int l, int r, int curr) {
int mid = (l + r) >> 1;
nodes[curr].numFromLeft = (nodes[curr << 1].value == (mid - l + 1)) ?
nodes[curr << 1].value + nodes[curr << 1 | 1].numFromLeft :
nodes[curr << 1].numFromLeft;
nodes[curr].numFromRight = (nodes[curr << 1 | 1].value == (r - mid)) ?
nodes[curr << 1 | 1].value + nodes[curr << 1].numFromRight :
nodes[curr << 1 | 1].numFromRight;
}
void pushUp(int l, int r, int curr) {
updateLeftRight(l, r, curr);
// considering merge sort
nodes[curr].value = max(
max(nodes[curr << 1].value, nodes[curr << 1 | 1].value),
nodes[curr << 1].numFromRight + nodes[curr << 1 | 1].numFromLeft
);
}
void pushDown(int l, int r, int curr) {
nodes[curr << 1].lazyType = nodes[curr << 1 | 1].lazyType = nodes[curr].lazyType;
int m = (l + r) >> 1;
if (nodes[curr].lazyType == REMOVE_ALL) {
nodes[curr << 1].numFromLeft = nodes[curr << 1].numFromRight = nodes[curr << 1].value = m - l + 1;
nodes[curr << 1 | 1].numFromLeft = nodes[curr << 1 | 1].numFromRight = nodes[curr << 1 | 1].value = r - m;
} else if (nodes[curr].lazyType == PLACE) {
nodes[curr << 1].numFromLeft = nodes[curr << 1].numFromRight = nodes[curr << 1].value = 0;
nodes[curr << 1 | 1].numFromLeft = nodes[curr << 1 | 1].numFromRight = nodes[curr << 1 | 1].value = 0;
}
nodes[curr].lazyType = 0;
}
void build(int left, int right, int curr) {
if (left == right) {
nodes[curr].numFromLeft = nodes[curr].numFromRight = nodes[curr].value = 1;
return;
}
int mid = (left + right) >> 1;
build(left, mid, curr << 1);
build(mid + 1, right, curr << 1 | 1);
pushUp(left, right, curr);
}
void update(int targetL, int targetR, int operationType, int l, int r, int curr) {
if (nodes[curr].lazyType != 0 && curr * 2 + 1 < mi)
pushDown(l, r, curr);
// the whole interval
if (targetL <= l && r <= targetR) {
if (operationType == REMOVE_ALL)
nodes[curr].numFromLeft = nodes[curr].numFromRight = nodes[curr].value = r - l + 1;
if (operationType == PLACE)
nodes[curr].numFromLeft = nodes[curr].numFromRight = nodes[curr].value = 0;
nodes[curr].lazyType = operationType;
return;
}
int mid = (l + r) >> 1;
if (targetL <= mid) update(targetL, targetR, operationType, l, mid, curr << 1);
if (targetR > mid) update(targetL, targetR, operationType, mid + 1, r, curr << 1 | 1);
pushUp(l, r, curr);
}
int query(int requiredSeats, int left, int right, int curr) {
if (nodes[curr].lazyType != 0)
pushDown(left, right, curr);
if (left == right)
return left;
int m = (left + right) >> 1;
// There are enough seats in the left part
if (nodes[curr << 1].value >= requiredSeats)
return query(requiredSeats, left, m, curr << 1);
// Cross two sub-intervals
else if (nodes[curr << 1].numFromRight + nodes[curr << 1 | 1].numFromLeft >= requiredSeats)
return m - nodes[curr << 1].numFromRight + 1;
// try to look for it in the right part
else
return query(requiredSeats, m + 1, right, curr << 1 | 1);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
// long start = System.currentTimeMillis();
// for (int i = 0; i < nodes.length; ++i)
// nodes[i] = new Node();
// long end = System.currentTimeMillis();
// System.out.println((end - start));
// System.exit(-1);
cin >> n >> m;
build(1, n, 1);
// int foo =(int) (Math.log(n)/Math.log(2) + 1) * 2;
// System.out.println(foo);
// System.exit(0);
int num = 0;
for (int i = 1; i <= m; i++) {
char cmd;
cin >> cmd;
if (cmd == 'A') {
int x;
cin >> x;
if (nodes[1].value >= x) {
int ans = query(x, 1, n, 1);
update(ans, ans + x - 1, PLACE, 1, n, 1);
} else num++;
} else {
int l, r;
cin >> l >> r;
update(l, r, REMOVE_ALL, 1, n, 1);
}
}
cout << num << endl;
} 来源：Bing_Bodybuilding
京公网安备 11010502036488号