题解 CF555C 【Case of Chocolate】

观察样例，发现格子被吃之后会被分割成这样几种形状： ```cpp 1. 跟原来长得一样 # # # # # # # # # # # # # # # ----------- 2.1 比原来多出一块（前几行）： # # # # # # # # # # # # # # # # # # # # # # # # # ----------- 2.2 比原来多出一块（前几列）： # # # # # # # # # # # # # # # # # # ----------- 3. 比原来多出两块： # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # ----------- 4. 某些矩形，肯定不会再被吃到 ``` 这样一来，一块区域就可以用四个量来表示：左右边界，向上和向左延伸的长度 用set维护即可： ```cpp #include <cstdio> #include <cstring> #include <algorithm> #include <set> using namespace std; int n, m, ans; class Squares { public: int l, r; int len_l, len_u; Squares() { l = r = 0; len_l = len_u = 0; } Squares(int _l, int _r, int _len_l, int _len_u) { l = _l, r = _r; len_l = _len_l, len_u = _len_u; } bool operator < (const Squares &b)const { return r < b.r; } } a, res, nxt; set<Squares> s; set<Squares>::iterator it; inline int read() { char ch = getchar(); int ret = 0, f = 1; while (ch > '9' || ch < '0') { if (ch == '-') f = -f; ch = getchar(); } while (ch >= '0' && ch <= '9') ret = ret * 10 + ch - '0', ch = getchar(); return ret * f; } int main() { // freopen("test.in", "r", stdin); // freopen("test.out", "w", stdout); n = read(), m = read(); res = Squares(1, n, 0, 0); s.insert(res); while (m--) { int x = read(), y = read(); char ch = getchar(); while (ch != 'U' && ch != 'L') ch = getchar(); a = Squares(x, x, 0, 0); it = s.lower_bound(a); if (it == s.end() || it->l > x || it->r < x) { printf("0\n"); continue; } res = *it; s.erase(it); if (ch == 'U') { ans = res.r - x + 1 + res.len_u; printf("%d\n", ans); if (x != res.l) { nxt = Squares(res.l, x - 1, res.len_l, ans); s.insert(nxt); } if (x != res.r) { nxt = Squares(x + 1, res.r, 0, res.len_u); s.insert(nxt); } } else { ans = x - res.l + 1 + res.len_l; printf("%d\n", ans); if (x != res.l) { nxt = Squares(res.l, x - 1, res.len_l, 0); s.insert(nxt); } if (x != res.r) { nxt = Squares(x + 1, res.r, ans, res.len_u); s.insert(nxt); } } } return 0; } ```