rmrs 题解

模拟赛 T3，好像是 lxl 的题。
题意

给定一个 \(n\times n\) 的二维平面，有 \(n\times n\) 个整点，每个整点都有权值，初始为 \(0\)。
有 \(n\) 次操作，每次操作给定一个矩形 \(x_1,x_2,y_1,y_2\) 和一个值 \(v\)，把这个矩形内的所有点的权值跟 \(v\) 取 \(\max\)。
在这 \(n\) 次操作之后，有 \(m\) 次询问，每次询问查询一个矩形的权值和。
数据范围： \(1\le n,m\le 10^5，1\le v \le n\)。
题解

直接考虑分块，把 \(x\) 轴分成 \(O(\sqrt{n})\) 个块，对于每个块内部会有一些零散的修改/查询，以及一些完整跨过这个块的修改/查询，下面对每个块单独考虑。
我们把这个块内部零散的修改/查询涉及到的 \(y\) 坐标离散化，设离散化后的 \(y\) 一共有 \(tot\) 个，那么所有块的 \(tot\) 之和是 \(O(n+m)\) 级别的。
我们称离散化之后的网格的每个点为一个格子，显然一个格子在原平面中代表一个在 \(x\) 轴方向上长为 \(1\) 的矩形。
因为修改都是在查询之前的，所以我们可以把修改离线下来按照 \(v\) 从大到小排序，这样的好处是每个点都只会被覆盖一次。

• 对散块修改：
  我们对每个 \(x\) 都开一个大小为 \(tot\) 的并查集，维护这个 \(x\) 坐标上哪些离散化之后的 \(y\) 还没有被覆盖，然后对散块的每个 \(x\) 都用并查集找到还没被覆盖的 \(y\) 进行覆盖。同时我们要对于每个离散化之后的 \(y\) 去维护有多少个真实的 \(x\) 已经被修改了（记作 \(c_1\)），以及这些修改操作的 \(v\) 之和（记作 \(s_1\)）。
  
• 对整块修改：
  我们开一个大小为 \(n\) 的并查集维护哪些真实的 \(y\) 还没有被修改，然后找到所有还没被修改的 \(y\) 进行修改。同时我们要对于每个离散化之后的 \(y\) 去维护有多少个真实的 \(y\) 已经被修改了（记作 \(c_2\)），以及这些修改操作的 \(v\) 之和（记作 \(s_2\)）。
  
• 对散块查询：
  对于散块查询，我们只需要提前处理出离散化之后的网格的二维前缀和即可。具体的，当我们进行散块修改时对 \((x,y)\) 这个格子（\(y\) 是离散化之后的）进行了覆盖，那么在这次操作之前，它里面已经有 \(c_2(y)\) 个真实的 \(y\) 被修改了，且权值和为 \(s_2(y)\)，我们可以算出这个格子中剩下还有多少个点没被覆盖，用它乘上这次操作的 \(v\) 再加上 \(s_2(y)\) 就是这个格子的权值。
  
• 对整块查询：
  类似的维护原始真实的 \(y\) 序列的前缀和即可。
  

不难分析出复杂度是 \(O(n\sqrt{n})\)（假设 \(n=m\)）。
code
[code]#include#define Debug puts("-------------------------")#define pb push_back#define LL long long#define PII pair#define fi first#define se second using namespace std;const int N=1e5+5,B=320;inline int read(){        int w=1,s=0;        char c=getchar();        for(;c'9';w*=(c=='-')?-1:1,c=getchar());        for(;c>='0'&&c