我好像写臭了最优解竟是我自己（2023/7/29）。
大概就是容斥一下，令：
- 至少被 \(1\) 种操作覆盖的格子数为 \(S_1\)（允许算重，即一个格子对 \(S_1\) 的贡献是它被覆盖的次数，下同）。
- 至少被 \(2\) 种操作覆盖的格子数为 \(S_2\)。
- 至少被 \(3\) 种操作覆盖的格子数为 \(S_3\)。
答案显然就是 \(S_1-S_2+S_3\)。
\(S_1\) 是好求的，考虑 \(S_2\) 和 \(S_3\)。
对于 \(S_2\)，分类讨论格子被哪两种操作覆盖。令 \(H\) 为覆盖行操作，\(L\) 为覆盖列操作，\(X\) 为覆盖斜线操作，只需枚举 \((A,B)\) 的无序操作二元组：
- \((H/L,X)\)：由于 \(X\) 操作不超过 \(5\) 次，直接对于每次 \(X\) 操作枚举所有的 \(H,L\) 操作，然后判断是否有交点即可。判断交点需要满足 \(2\) 个条件，斜线的两个端点在水平/竖直线的两侧，以及解出来的交点在水平/竖直线的覆盖范围内。
- \((H,L)\)：即求所有行操作和列操作的交点个数，直接扫描线即可。
对于 \(S_3\)，类似 \(S_2(H/L,X)\) 的做法，枚举 \(X\) 操作，枚举 \(L\) 操作，算出 \(X,L\) 两个操作的交点，我们求出有多少个 \(H\) 操作经过这个交点即可。也可以用扫描线解决。
复杂度 \(O(q\log q)\)。
#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); }), 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;
}