题意：给出若干个形如 \(x\le X_i,x\ge X_i,y\le Y_i,y\ge Y_i\) 的覆盖，每个覆盖代价为 \(c\)，要求平面上每个点被覆盖至少 \(k\) 次，求最小代价。
做法：
考虑一维怎么做，发现我们需要若干个形如 \(x\le a, x\ge b,b\le a\) 的形式才行，那么就等于一个括号匹配，选出 \(k\) 对，这个显然是凸的，wqs 完之后用优先队列选出尽量多的代价 \(\le 0\) 的匹配即可。
然后是二维，我们发现其实对于两维是完全独立的，手玩一下可以知道，然后因为两边都是凸的，所以总的也是满足凸的，所以同时 wqs 直接合并即可，对两维分别做即可，复杂度 \(O(n\log n\log V)\)。
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5 + 5;
int n, k;
struct node {int op, x, c;friend bool operator<(node x, node y) {return (x.x != y.x ? x.x < y.x : x.op > y.op);}
} x[2][maxn];
int tot[2];
struct Stu {int val, c;friend bool operator<(Stu x, Stu y) {return (x.val != y.val ? x.val > y.val : x.c > y.c);}
};
priority_queue<Stu> q;
int res;
int cal(int k, int d) {while(!q.empty()) q.pop();int ans = 0; for (int i = 1; i <= tot[k]; i++) {if(x[k][i].op == 2)q.push(Stu{x[k][i].c, 1});else {if(!q.empty() && q.top().val + x[k][i].c + d <= 0) {res += q.top().val + x[k][i].c + d;ans += q.top().c; q.pop();q.push(Stu{-x[k][i].c - d, 0});}}}return ans;
}
signed main() {cin >> n >> k;for (int i = 1; i <= n; i++) {int op, xt, y, c;cin >> op >> xt >> y >> c;if(op <= 2)x[0][++tot[0]] = node{op, xt, c};elsex[1][++tot[1]] = node{op - 2, y, c};}sort(x[0] + 1, x[0] + tot[0] + 1);sort(x[1] + 1, x[1] + tot[1] + 1);int l = -1e13, r = 0;while(l + 1 < r) {int mid = l + r >> 1;res = 0;if(cal(0, mid) + cal(1, mid) >= k)l = mid;elser = mid;}res = 0;int t = cal(0, l) + cal(1, l);if(t < k) cout << -1 << endl;elsecout << res - l * k << endl;return 0;
}