【HT周赛】T3.二维平面 题解（分块：矩形chkmax，求矩形和）

题意

需要维护 $n\times n$ 平面上的整点，每个点 $(x,y)$ 有权值 $V(x,y)$，初始都为 $0$。

同时给定 $n$ 次修改操作，每次修改给出 $x_1,x_2,y_1,y_2,v$，对每个满足 $x_1\le x\le x_2,y_1\le y\le y_2$ 的 $(x,y)$，将 $V(x,y)$ 修改为 $\max (V(x,y),v)$。

在所有修改操作进行完后，有 $m$ 次查询操作，每次给出 $x_1,x_2,y_1,y_2$，查询 $\sum _{x=x_1}^{x_2}\sum _{y=y_1}^{y_2}V(x,y)$。

$1\le n,m\le 2\times 10^5$。
$1\le x_1\le x_2\le n,1\le y_1\le y_2\le n,1\le v\le n$。

分析

本题需要我们实现 矩形 $chkmax$，求矩形和。

首先定义水平方向从左到右 $x$ 递增， 竖直方向自上到下 $y$ 递增。

一般的 离线矩形操作 是通过 矩形扫描线 解决的。比如 矩形加， 求矩形和，可以通过扫描线维护历史版本和的方法在 $O(n\log n)$ 的复杂度内求出答案。但是对于 $chkmax$ 操作，它很难撤销并且维护矩阵也比较困难。因次矩形扫描线是行不通的。

考虑 分块：
具体来说，设阈值为 $B$，将 $x$ 轴按照 $B$ 为段长分成若干 $B\times n$ 的细长矩形，对这 $\frac{n}{B}$ 个细长矩形分别考虑所有修改的影响以及所有查询在这一部分内的答案。

将与当前处理的细长矩形有交的 询问矩形和修改矩形 分成两类： $x$ 坐标完全跨过当前矩形的 和 $x$ 坐标不完全跨过的。如下图所示：

将 第二类矩形 上下边界的 $y$ 坐标取出来进行离散化。那么会得到一个 $B\times c$ 的网格，其中 $c$ 表示第二类矩形的数量。

由于一个修改/查询矩形最多会在两个块内作为第二类矩形，因此所有 $c$ 的和为 $O(m)$，得到的总网格数为 $O(Bm)$。

考虑此时怎么维护修改和查询：对于第二类矩形，修改/查询的范围对应了网格图上的一个矩形。对于第一类矩形，修改/查询的范围对应了离散化前 $y$ 坐标上连续的若干行（注意因为我们没有离散化第一类矩形的 $y$ 坐标，所以这些 $y$ 可能并不能对应网格图上的一个 $y^{\prime }$）。

由于第一类矩形的存在，仅有一张网格图是不够的。考虑同时维护一个长为 $n$ 的数组 $A$ 表示将 $B$ 列压缩成一列后的每一行。我们希望能够维护出所有修改操作后 网格图上每个格子的权值 以及 $A$ 数组每个位置的权值，这样只需要在网格图上求一遍二位前缀和，对 $A$ 数组求一遍前缀和，就可以 $O(1)$ 回答出所有询问的答案。

将所有修改矩形按照 $v$ 从大到小排序，那么 $chkmax$ 就变成了覆盖。
我们发现所有细长矩形中 网格的总数和 $A$ 的长度之和为 $O(Bm+\frac{n^2}{B})$，取 $B=\frac{n}{\sqrt{m}}$，可以得到 $O(Bm+\frac{n^2}{B})=O(n\sqrt{m})$，那么暴力覆盖就是对的。

我们对网格图的 $B$ 列维护一个长度为 $c$ 的并查集，同时对 $A$ 维护一个长为 $n$ 的并查集，染色过程中跳过之前已经被染过色的位置。考虑如何计算答案：如果要染色一行，那么我们需要知道这一行对应到的网格图的某一行已经被染色的格子数量，以及覆盖这些格子的权值之和。如果要染色一个格子，我们需要知道这个格子的 $y^{\prime }$ 对应到原来的 $y$ 的一段区间中，有多少行已经被染色，以及行染色的权值之和。这些信息都可以在染色一行或一个格子时维护。

最后需要将所有没染色的格子和行求出它们现在的权值和。（因为会受到另一种覆盖的影响）
然后求一遍前缀和即可。复杂度 $O(m\sqrt{n})$。

// 矩形 chkmax， 矩形求和 
#include<bits/stdc++.h>
#define pb emplace_back
using namespace std;
struct IO{static const int S=1<<21;char buf[S],*p1,*p2;int st[105],Top;~IO(){clear();}inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}inline void pc(const char c){Top==S&&(clear(),0);buf[Top++]=c;}inline char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}inline IO&operator >> (char&x){while(x=gc(),x==' '||x=='\n'||x=='\r');return *this;}template<typename T>inline IO&operator >> (T&x){x=0;bool f=0;char ch=gc();while(!isdigit(ch)){if(ch=='-') f^=1;ch=gc();}while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=gc();f?x=-x:0;return *this;}inline IO&operator << (const char c){pc(c);return *this;}template<typename T>inline IO&operator << (T x){if(x<0) pc('-'),x=-x;do{st[++st[0]]=x%10,x/=10;}while(x);while(st[0]) pc('0'+st[st[0]--]);return *this;}
}fin, fout;
const int N = 2e5 + 10;
const int M = 205;
typedef long long LL;
struct OP {int lx, rx, ly, ry, v;friend bool operator < (OP a, OP b) {return a.v > b.v;}
} opt[N * 2];
struct Union {int n, bin[N];int Find(int x) {return x == bin[x] ? x : bin[x] = Find(bin[x]);}inline void init(int _n) {n = _n; for(int i = 1; i <= n; i ++ ) bin[i] = i;}inline void Merge(int x) {if(x != n) bin[x] = Find(x + 1);}// 将 x 和它的下一个合并 inline int nxt(int x) {return Find(x + 1);}
} L[M], U;
int n, m, tmp[N * 2], tot;
int Y[N], bel[N], cnt;
bool exs[N];
LL ans[N], mp[M][N], sum[N], S1[N], C1[N], S2[N], C2[N]; // S1, C1 是网格染色的信息。 S2, C2 是行染色的信息 
inline void solve(int l, int r) { // 首先先把散块修改和询问的 y 坐标离散化	vector< int > pos;exs[0] = exs[n] = 1; tot = 0; cnt = 0; int st = -1;for(int i = 1; i <= n + m; i ++ ) {if(opt[i].rx < l || opt[i].lx > r) continue;tmp[++ tot] = i;if(opt[i].lx <= l && opt[i].rx >= r) ;else exs[opt[i].ly - 1] = exs[opt[i].ry] = 1;if(opt[i].v == 0) st = (st == -1 ? tot : st);}if(st == -1) return ;int lst = 0;for(int i = 0; i <= n; i ++ ) {bel[i] = lst;if(exs[i]) pos.pb(i), Y[++ cnt] = i, lst ++; // 离散化所有纵坐标 }for(int i = 1; i <= r - l + 1; i ++ ) L[i].init(cnt); // 第 i 个距离是 Y_{i + 1} - Y_i for(int i = 1; i < cnt; i ++ ) S1[i] = C1[i] = S2[i] = C2[i] = 0;U.init(n + 1);for(int i = 1; i <= tot; i ++ ) {int o = tmp[i];if(!opt[o].v) break;if(opt[o].lx <= l && opt[o].rx >= r) { // 染一行 for(int j = U.Find(opt[o].ly); j <= opt[o].ry; j = U.nxt(j)) {sum[j] = S1[bel[j]] + ((r - l + 1) - C1[bel[j]]) * opt[o].v;C2[bel[j]] ++; S2[bel[j]] += opt[o].v;U.Merge(j);}}else { // 染若干格子 for(int x = max(l, opt[o].lx) - l + 1; x <= min(r, opt[o].rx) - l + 1; x ++ ) {for(int j = L[x].Find(bel[opt[o].ly]); j <= bel[opt[o].ry]; j = L[x].nxt(j)) {mp[x][j] = S2[j] + (Y[j + 1] - Y[j] - C2[j]) * opt[o].v;C1[j] ++; S1[j] += opt[o].v;L[x].Merge(j);}}}}// 接下来确定还没染色的所有格子 for(int i = 1; i <= r - l + 1; i ++ ) for(int j = 1; j < cnt; j ++ ) {if(L[i].Find(j) == j) mp[i][j] = S2[j];mp[i][j] = mp[i - 1][j] + mp[i][j - 1] + mp[i][j] - mp[i - 1][j - 1];}for(int i = 1; i <= n; i ++ ) {if(U.Find(i) == i) sum[i] = S1[bel[i]];sum[i] += sum[i - 1];}	for(int i = st; i <= tot; i ++ ) { // 处理所有询问 int o = tmp[i];if(opt[o].lx <= l && opt[o].rx >= r) ans[o - n] += sum[opt[o].ry] - sum[opt[o].ly - 1];else {int lx = max(opt[o].lx, l) - l + 1, rx = min(opt[o].rx, r) - l + 1, ly = bel[opt[o].ly], ry = bel[opt[o].ry];ans[o - n] += mp[rx][ry] - mp[rx][ly - 1] - mp[lx - 1][ry] + mp[lx - 1][ly - 1];}}for(auto v : pos) exs[v] = 0;
}
int main() {fin >> n >> m;for(int i = 1; i <= n; i ++ ) fin >> opt[i].lx >> opt[i].rx >> opt[i].ly >> opt[i].ry >> opt[i].v;for(int i = 1; i <= m; i ++ ) fin >> opt[i + n].lx >> opt[i + n].rx >> opt[i + n].ly >> opt[i + n].ry;stable_sort(opt + 1, opt + n + m + 1);int B = min((int)sqrt(n), 200);for(int i = 1; i <= n; i += B ) solve(i, min(i + B - 1, n));for(int i = 1; i <= m; i ++ ) fout << ans[i], fout.pc('\n');return 0;
}