Seating
时间限制: 1 Sec 内存限制: 64 MB
题目描述
To earn some extra money, the cows have opened a restaurant in their barn specializing in milkshakes. The restaurant has N seats (1 <= N <= 500,000) in a row. Initially, they are all empty.
Throughout the day, there are M different events that happen in sequence at the restaurant (1 <= M <= 300,000). The two types of events that can happen are:
1. A party of size p arrives (1 <= p <= N). 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 (1 <= a <= b <= N), 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, N and M.
* Lines 2..M+1: Each line describes a single event. It is either a line of the form "A p" (meaning a party of size p arrives) or "L a b" (meaning that all cows in the range [a, b] leave).
输出
* Line 1: The number of parties that are turned away.
样例输入
|
1 2 3 4 5 |
10 4 A 6 L 2 4 A 5 A 2 |
样例输出
|
1 |
1 |
提示
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.Party #3 is turned away. All other parties are seated.
题解
主要是通过线段树求是否存在某个区间是否有连续的p个1，如果有，找出最靠左的这样的一个长度为p的区间。
比较复杂的线段树，类似小白逛公园。这里的做法可能比较麻烦，线段树维护四个值，每个区间左边连续1的个数lval，中间连续1的个数midval，右边连续1的个数rval，及整个区间中最多的连续的1的个数max。查询时如果当前区间max<p直接就是找不到符合要求的区间，返回-1；如果当前区间的max>=p，则这个>p的值可能在左边子区间，中间子区间，或右子区间。如果当前区间的lval>=p，则直接返回当前区间的左端点即可；如果左子区间的max>=p则在左子区间，继续向左子区间查询；若不在左子区间，当前区间的midval>=p的话，最靠左的符合要求的区间的左端点为midval-左子区间rval+1；否则继续向右子区间查询。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 |
#include <bits/stdc++.h> #define lc rt << 1 #define rc rt << 1 | 1 using namespace std; typedef long long LL; const int N = 500009; class SegmentTree { public: void build(int l, int r, int rt) { t[rt].lval = t[rt].rval = t[rt].midval = t[rt].max = r - l + 1; t[rt].lzy = -1; if(l>=r) return; int mid = (l + r) >> 1; build(l, mid, lc); build(mid + 1, r, rc); pushup(rt, l, mid, r); } void update(int l, int r, int rt, int L, int R, int v) { if(r < L || l > R || l > r || L > R) return; if(L <= l && r <= R) { t[rt].lzy = v; t[rt].lval = t[rt].midval = t[rt].rval = t[rt].max = (r - l + 1) * v; return; } int mid = (l + r) >> 1; pushdown(rt, l, mid, r); update(l, mid, lc, L, R, v); update(mid + 1, r, rc, L, R, v); pushup(rt, l, mid, r); } int query(int l, int r, int rt, int len) { if(Max(rt)<len) return -1; int mid = (l + r) >> 1; if(t[rt].lval >= len) return l; pushdown(rt, l, mid, r); int ans = -1; if(Max(lc) >= len) { ans = query(l, mid, lc, len); pushup(rt, l, mid, r); } else if(t[rt].midval >= len) ans = mid - t[lc].rval + 1; else if(Max(rc) >= len) { ans = query(mid + 1, r, rc, len); pushup(rt, l, mid, r); } return ans; } private: struct Node { int lval, rval, midval, lzy, max; }; Node t[4 * N]; int Max(int rt) { return max(max(t[rt].lval, t[rt].max), max(t[rt].midval, t[rt].rval)); } void pushup(int rt, int l, int mid, int r) { if(t[lc].lval >= mid - l + 1) t[rt].lval = t[lc].lval + t[rc].lval; else t[rt].lval = t[lc].lval; if(t[rc].rval >= r - mid) t[rt].rval = t[rc].rval + t[lc].rval; else t[rt].rval = t[rc].rval; t[rt].midval = t[lc].rval + t[rc].lval; t[rt].max = 0; t[rt].max = max(Max(rt), max(Max(lc), Max(rc))); } void pushdown(int rt, int l, int mid, int r) { if(t[rt].lzy == -1) return; t[lc].lzy = t[rc].lzy = t[rt].lzy; t[lc].lval = t[lc].midval = t[lc].rval = t[lc].max = (mid - l + 1) * t[rt].lzy; t[rc].lval = t[rc].midval = t[rc].rval = t[rc].max = (r - mid) * t[rt].lzy; t[rt].lzy = -1; } }; SegmentTree t; int n, m; int main() { #ifndef ONLINE_JUDGE freopen("input.in", "r", stdin); freopen("output.out", "w", stdout); #endif scanf("%d%d", &n, &m); t.build(1, n, 1); int ans = 0; for (int i = 1; i <= m; i++) { char op[2]; scanf("%s", op); if(op[0]=='A') { int x; scanf("%d", &x); int k = t.query(1, n, 1, x); if(k==-1) { ans++; continue; } t.update(1, n, 1, k, k + x - 1, 0); } else { int l, r; scanf("%d%d", &l, &r); t.update(1, n, 1, l, r, 1); } } printf("%d\n", ans); return 0; } |
叨叨几句... NOTHING