题意：给出一个平面和 \(n\) 次操作，还有一个参数 \(X\)，多次询问矩形加法后，用一个矩形覆盖住所有大于等于 \(X\) 的元素，至少需要多大面积的矩形。\(n\le 2\times 10^5\)。
做法：
考虑维护每个时刻最左，右，上，下四条边满足有至少为 \(X\) 的元素的边界，答案可以简单计算，重点是怎么计算这个边界。
直接维护很难，可以上数据结构手法一下但是这也太傻了，究其原因是因为当我们要外拓展的时候不知道有没有答案。但是我们可以这样，倒序考虑，这样如果当前的边界不为答案就无脑往里缩就可以，扫描一下维护一下即可，复杂度 \(O(n\log n)\)。
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 8e5 + 5;
int h, w, n, x;
struct Seg {int l, r, c, id, p;
} ;
vector<Seg> vec[maxn];
int ls[maxn], tot;
int qpos(int x) {return lower_bound(ls + 1, ls + tot + 1, x) - ls;
}
int u[maxn], d[maxn], l[maxn], r[maxn], c[maxn], ans[2][maxn];
struct Segtree {int tr[maxn << 2], tag[maxn << 2];void pushup(int t) {tr[t] = max(tr[t << 1], tr[t << 1 | 1]);}void addtag(int t, int val) {tag[t] += val, tr[t] += val;}void pushdown(int t) {addtag(t << 1, tag[t]);addtag(t << 1 | 1, tag[t]);tag[t] = 0;}void build(int l, int r, int t) {tag[t] = tr[t] = 0;if(l == r)return ;int mid = l + r >> 1;build(l, mid, t << 1), build(mid + 1, r, t << 1 | 1);pushup(t);}void update(int l, int r, int x, int y, int t, int val) {//cout << x << " solve" << y << " " << val << " " << l << " " << r << endl;if(x <= l && r <= y) {addtag(t, val);return ;}pushdown(t);int mid = l + r >> 1;if(x <= mid)update(l, mid, x, y, t << 1, val);if(mid < y)update(mid + 1, r, x, y, t << 1 | 1, val);pushup(t);}
} tree;
void solve(int k) {int p = 1;tree.build(1, tot, 1);for (int i = 0; i < vec[1].size(); i++)if(vec[1][i].id == 1)tree.update(1, tot, vec[1][i].l, vec[1][i].r, 1, vec[1][i].c);while(p <= tot && tree.tr[1] < x) {for (int i = 0; i < vec[p].size(); i++)if(vec[p][i].id == 2)tree.update(1, tot, vec[p][i].l, vec[p][i].r, 1, -vec[p][i].c);p++;for (int i = 0; i < vec[p].size(); i++)if(vec[p][i].id == 1)tree.update(1, tot, vec[p][i].l, vec[p][i].r, 1, vec[p][i].c);}for (int i = n; i >= 1; i--) {ans[k][i] -= ls[p];// cout << i << " " << p << " " << ls[p]<< endl;int lx = (k == 0 ? l[i] : d[i]), rx = (k == 0 ? r[i] : u[i]), lt = (k == 0 ? d[i] : l[i]), rt = (k == 0 ? u[i] : r[i]);if(lx <= p && rx >= p) tree.update(1, tot, lt, rt, 1, -c[i]);while(p <= tot && tree.tr[1] < x) {for (int j = 0; j < vec[p].size(); j++)if(vec[p][j].id == 2 && vec[p][j].p < i)tree.update(1, tot, vec[p][j].l, vec[p][j].r, 1, -vec[p][j].c);p++;for (int j = 0; j < vec[p].size(); j++)if(vec[p][j].id == 1 && vec[p][j].p < i) {// cout << "asdfsadlgkj" << vec[p][j].id << endl;tree.update(1, tot, vec[p][j].l, vec[p][j].r, 1, vec[p][j].c);}}}
// cout << "adsf" << endl;p = tot;tree.build(1, tot, 1);for (int i = 0; i < vec[tot].size(); i++)if(vec[tot][i].id == 2)tree.update(1, tot, vec[tot][i].l, vec[tot][i].r, 1, vec[tot][i].c);while(p && tree.tr[1] < x) {for (int i = 0; i < vec[p].size(); i++)if(vec[p][i].id == 1)tree.update(1, tot, vec[p][i].l, vec[p][i].r, 1, -vec[p][i].c);p--;for (int i = 0; i < vec[p].size(); i++)if(vec[p][i].id == 2)tree.update(1, tot, vec[p][i].l, vec[p][i].r, 1, vec[p][i].c);}
// cout << p << "asdf" << endl;for (int i = n; i >= 1; i--) {// cout << p << " " << ls[p] << " " << ans[k][1] << endl;ans[k][i] += ls[p] + 1;int lx = (k == 0 ? l[i] : d[i]), rx = (k == 0 ? r[i] : u[i]), lt = (k == 0 ? d[i] : l[i]), rt = (k == 0 ? u[i] : r[i]);if(lx <= p && rx >= p) tree.update(1, tot, lt, rt, 1, -c[i]);while(p && tree.tr[1] < x) {for (int j = 0; j < vec[p].size(); j++)if(vec[p][j].id == 1 && vec[p][j].p < i)tree.update(1, tot, vec[p][j].l, vec[p][j].r, 1, -vec[p][j].c);p--;for (int j = 0; j < vec[p].size(); j++)if(vec[p][j].id == 2 && vec[p][j].p < i)tree.update(1, tot, vec[p][j].l, vec[p][j].r, 1, vec[p][j].c);}// cout << i << " " << ls[p] << " " << p << " " << tree.tr[1] << " debug" << lx << " " << rx << endl;}
}
signed main() {cin >> h >> w >> n >> x;for (int i = 1; i <= n; i++) {cin >> u[i] >> d[i] >> l[i] >> r[i] >> c[i];swap(u[i], d[i]);ls[++tot] = u[i], ls[++tot] = d[i];ls[++tot] = l[i], ls[++tot] = r[i];}sort(ls + 1, ls + tot + 1); tot = unique(ls + 1, ls + tot + 1) - ls - 1;for (int i = 1; i <= n; i++) {u[i] = qpos(u[i]), d[i] = qpos(d[i]);l[i] = qpos(l[i]), r[i] = qpos(r[i]);}ls[tot + 1] = 1;for (int i = 1; i <= tot; i++)vec[i].clear();for (int i = 1; i <= n; i++)vec[l[i]].push_back(Seg{d[i], u[i], c[i], 1, i}),vec[r[i]].push_back(Seg{d[i], u[i], c[i], 2, i});solve(0);for (int i = 1; i <= tot; i++)vec[i].clear();for (int i = 1; i <= n; i++)vec[d[i]].push_back(Seg{l[i], r[i], c[i], 1, i}),vec[u[i]].push_back(Seg{l[i], r[i], c[i], 2, i});solve(1);for (int i = 1; i <= n; i++)cout << ans[0][i] * ans[1][i] << endl;return 0;
}