考虑最大权闭合子图，第 \(i\) 个手办建点 \(i\)，第 \(i\) 个警察建点 \(i'\)。我们有一些边：\(\forall i, (S, i, v_i), (i', T, v_i)\)，以及对于能看见第 \(i\) 个手办的第 \(j\) 个警察，有 \((i, j', \infty)\)。手办的 \(\sum v_i\) 减去最小割（最大流）即为答案。
考虑转换坐标系，\((x, y) \to (hx + wy, hx - wy)\)。那么第 \(i\) 个警察能看见第 \(j\) 个手办当且仅当 \(x_i \ge x_j \land y_i \le y_j\)。
但是显然最大流复杂度会炸。考虑模拟最大流。下面部分和 CF1895G Two Characters, Two Colors 有点类似。
首先显然把警察和手办都按 \(x\) 排序。那么我们扫警察时可以先处理 \(x\) 这维的偏序。
我们可以先让 \(v_i\) 的流量从 \(S\) 流到 \(i\)。然后用一个二元组 \((y, v)\) 表示一个纵坐标为 \(y\) 的点还有 \(v\) 单位流量。那么我们扫警察时把所有 \(x\) 比它小的二元组加入。
然后我们现在对于一个警察，它还能往汇点流 \(v_i\) 的流量。考虑贪心地从 \(y\) 坐标不小于它且最小的二元组获取流量。因为 \(y\) 越小的二元组可能的连边就越少，我们从 \(y\) 更大的二元组获取流量不会变优。
所以我们用 set 维护这些二元组，就可以直接 lower_bound 找对应的二元组了。
时间复杂度 \(O((n + m) \log m)\)。
code
// Problem: P5996 [PA2014] Muzeum
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5996
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
ll n, m, A, B;
struct node {
ll x, y, z;
} a[maxn], b[maxn];
void solve() {
scanf("%lld%lld%lld%lld", &n, &m, &A, &B);
ll ans = 0;
for (int i = 1; i <= n; ++i) {
scanf("%lld%lld%lld", &a[i].x, &a[i].y, &a[i].z);
ll x = a[i].x * B + a[i].y * A, y = a[i].x * B - a[i].y * A;
a[i].x = x;
a[i].y = y;
ans += a[i].z;
}
for (int i = 1; i <= m; ++i) {
scanf("%lld%lld%lld", &b[i].x, &b[i].y, &b[i].z);
ll x = b[i].x * B + b[i].y * A, y = b[i].x * B - b[i].y * A;
b[i].x = x;
b[i].y = y;
}
sort(a + 1, a + n + 1, [&](const node &a, const node &b) {
return a.x < b.x;
});
sort(b + 1, b + m + 1, [&](const node &a, const node &b) {
return a.x < b.x;
});
multiset<pii> S;
for (int i = 1, j = 1; i <= m; ++i) {
while (j <= n && a[j].x <= b[i].x) {
S.emplace(a[j].y, a[j].z);
++j;
}
ll d = b[i].z;
while (d && S.size()) {
auto it = S.lower_bound(mkp(b[i].y, 0));
if (it == S.end()) {
break;
}
pii p = *it;
S.erase(it);
ll mn = min(d, p.scd);
d -= mn;
p.scd -= mn;
ans -= mn;
if (p.scd) {
S.insert(p);
}
}
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}