NOI2023 方格染色

· · 题解

upd 2023/10/17 : 被人叉了，改了一下。/kk

更优质的阅读体验。

大概就是容斥一下，令：

答案显然就是 S_1-S_2+S_3。

对于 $S_2$，分类讨论格子被哪两种操作覆盖。令 $H$ 为覆盖行操作，$L$ 为覆盖列操作，$X$ 为覆盖斜线操作，只需枚举 $(A,B)$ 的无序操作二元组： 1. $(H/L,X)$：由于 $X$ 操作不超过 $5$ 次，直接对于每次 $X$ 操作枚举所有的 $H,L$ 操作，然后判断是否有交点即可。判断交点需要满足 $2$ 个条件，斜线的两个端点在水平/竖直线的两侧，以及解出来的交点在水平/竖直线的覆盖范围内。 2. $(H,L)$：即求所有行操作和列操作的交点个数，直接扫描线即可。 对于 $S_3$，类似 $S_2(H/L,X)$ 的做法，枚举 $X$ 操作，枚举 $L$ 操作，算出 $X,L$ 两个操作的交点，我们求出有多少个 $H$ 操作经过这个交点即可。也可以用扫描线解决。 复杂度 $O(q\log q)$。 注意第三种操作排序要双关键字。 ```cpp #include <bits/stdc++.h> #define ll long long using namespace std; namespace vbzIO { char ibuf[(1 << 20) + 1], *iS, *iT; #if ONLINE_JUDGE #define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++) #else #define gh() getchar() #endif #define mt make_tuple #define mp make_pair #define fi first #define se second #define pc putchar #define pb emplace_back #define ins insert #define era erase typedef tuple<int, int, int> tu3; typedef pair<int, int> pi; inline int rd() { char ch = gh(); int x = 0; bool t = 0; while (ch < '0' || ch > '9') t |= ch == '-', ch = gh(); while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh(); return t ? ~(x - 1) : x; } inline void wr(ll x) { if (x < 0) x = ~(x - 1), pc('-'); if (x > 9) wr(x / 10); pc(x % 10 + '0'); } } using namespace vbzIO; const int Q = 1e5 + 100; int n, m, tq; ll ans; vector<tu3> q[3], t; set<tu3> st; map<int, int> ctx, cty; #define gt(x, y) (get<x>(y)) void dl(int op) { t.clear(); for (int i = 0; i < q[op].size(); i++) { int r = i; if (op <= 1) while (r < q[op].size() - 1 && gt(0, q[op][r + 1]) == gt(0, q[op][i])) r++; else while (r < q[op].size() - 1 && gt(0, q[op][r + 1]) - gt(1, q[op][r + 1]) == gt(0, q[op][i]) - gt(1, q[op][i])) r++; st.clear(); for (int j = i; j <= r; j++) { auto [y, xl, xr] = q[op][j]; xr = xl + xr - 1; if (st.empty()) st.ins(mt(xr, xl, y)); else if (gt(0, *st.rbegin()) >= xl) { auto [tr, tl, tt] = *st.rbegin(); st.era(mt(tr, tl, tt)), st.ins(mt(max(xr, tr), min(tl, xl), min(tt, y))); } else st.ins(mt(xr, xl, y)); } for (auto [tr, tl, tt] : st) t.pb(mt(tt, tl, tr - tl + 1)); i = r; } q[op] = t; } struct BIT { int tr[Q * 3], n; BIT () { } BIT (int len) { memset(tr, 0, sizeof(int) * (len + 10)), n = len; } int lb(int x) { return x & (-x); } void upd(int x, int y) { for (int i = x; i <= n; i += lb(i)) tr[i] += y; } int qry(int x) { int res = 0; for (int i = x; i; i -= lb(i)) res += tr[i]; return res; } int qlr(int l, int r) { return qry(r) - qry(l - 1); } }; int Sub1() {// x, h, l static int tp[Q << 1], ts[Q]; int res = 0, len = 0, k = 0; vector<pi> qr; vector<tu3> op; for (auto [x, y, le] : q[2]) for (auto [ty, xl, xr] : q[0]) if (1ll * (y - ty) * (y + le - 1 - ty) <= 0 && xl <= x + ty - y && x + ty - y <= xl + xr - 1) qr.pb(mp(ty, x + ty - y)), tp[++len] = x + ty - y; for (auto [x, l, r] : q[1]) op.pb(mt(l, x, 1)), op.pb(mt(l + r, x, -1)), tp[++len] = x; sort(qr.begin(), qr.end()), sort(op.begin(), op.end()); sort(tp + 1, tp + len + 1), len = unique(tp + 1, tp + len + 1) - tp - 1; for (auto &[x, y] : qr) y = lower_bound(tp + 1, tp + len + 1, y) - tp; for (auto &[x, y, z] : op) y = lower_bound(tp + 1, tp + len + 1, y) - tp; memset(ts, 0, sizeof(int) * (len + 10)); for (auto [x, y] : qr) { while (k < op.size() && gt(0, op[k]) <= x) ts[gt(1, op[k])] += gt(2, op[k]), k++; res += ts[y]; } return res; } int Sub2() {// x, l int res = 0; for (auto [x, y, len] : q[2]) for (auto [ty, xl, xr] : q[0]) if (1ll * (y - ty) * (y + len - 1 - ty) <= 0 && xl <= x + ty - y && x + ty - y <= xl + xr - 1) res++; return res; } int Sub3() {// x, h int res = 0; for (auto [x, y, len] : q[2]) for (auto [tx, yl, yr] : q[1]) if (1ll * (x - tx) * (x + len - 1 - tx) <= 0 && yl <= y + tx - x && y + tx - x <= yl + yr - 1) res++; return res; } ll Sub4() {// h, l static int tp[Q * 3]; ll res = 0, len = 0, k = 0; vector<tu3> qr, op; for (auto [ty, xl, xr] : q[0]) qr.pb(mt(ty, xl, xl + xr - 1)), tp[++len] = xl, tp[++len] = xl + xr - 1; for (auto [tx, yl, yr] : q[1]) op.pb(mt(yl, tx, 1)), op.pb(mt(yl + yr, tx, -1)), tp[++len] = tx; sort(qr.begin(), qr.end()), sort(op.begin(), op.end()); sort(tp + 1, tp + len + 1), len = unique(tp + 1, tp + len + 1) - tp - 1; for (auto &[x, y, z] : qr) y = lower_bound(tp + 1, tp + len + 1, y) - tp, z = lower_bound(tp + 1, tp + len + 1, z) - tp; for (auto &[x, y, z] : op) y = lower_bound(tp + 1, tp + len + 1, y) - tp; BIT B = BIT(len); for (auto [x, y, z] : qr) { while (k < op.size() && gt(0, op[k]) <= x) B.upd(gt(1, op[k]), gt(2, op[k])), k++; res += B.qlr(y, z); } return res; } signed main() { rd(), n = rd(), m = rd(), tq = rd(); while (tq--) { int op = rd(), xa = rd(), ya = rd(), xb = rd(), yb = rd(); if (op == 1) { if (xa > xb) swap(xa, xb), swap(ya, yb); q[0].pb(mt(ya, xa, xb - xa + 1)); } else if (op == 2) { if (ya > yb) swap(xa, xb), swap(ya, yb); q[1].pb(mt(xa, ya, yb - ya + 1)); } else { if (xa > xb) swap(xa, xb), swap(ya, yb); q[2].pb(mt(xa, ya, xb - xa + 1)); } } for (int i = 0; i <= 1; i++) sort(q[i].begin(), q[i].end()), dl(i); sort(q[2].begin(), q[2].end(), [](tu3 &x, tu3 &y) { return gt(0, x) - gt(1, x) == gt(0, y) - gt(1, y) ? gt(0, x) < gt(0, y) : gt(0, x) - gt(1, x) < gt(0, y) - gt(1, y); }), dl(2); for (int i = 0; i <= 2; i++) for (auto [x, l, r] : q[i]) ans += r; ans = ans - Sub2() - Sub3() + Sub1() - Sub4(); wr(ans); return 0; } ```