P0 一些闲话
数据结构专题一般都需要一些套路或者巧妙转化，变成板子之后再维护。
例如这是一道 普及组线段树模板题 神题。
P1 基本思路
有了之前几题的铺垫，可以想到对值域开一个线段树，去维护前缀的信息再判断能否组成一个矩形。
考虑套用之前判断值域连续区间的套路，即维护前缀点集合中的 $Min_x, Max_x, Min_y, Max_y$，一个值域前缀 $i$ 满足条件仅当 $(Max_x - Min_x + 1) \times (Max_y - Min_y + 1) = i$。
这貌似是可行的，移项之后维护有多少个位置是 $0$ 即可。但是本题有修改，而前缀 $\max,\min$ 的修改是 $O(n)$ 的复杂度，显然无法通过。
有一个非常巧妙的转化：把 $[1,i]$ 的所有点染成黑色，$(i,n]$ 的点染成白色。
对于每一个前缀，计算如下两个值：
$t_1$ 表示有多少个黑点左边和上边都是白色或边界。
$t_2$ 表示有多少个白点的四联通位置有 $\geq 2$ 个黑点。
对于矩形来说，满足 $t_1=1,t_2=0$，那满足这个条件的都是矩形吗？
显然，$t_1=1$ 说明了只有一个连通块，而 $t_2=0$ 说明这个连通块是“凸的”，即不存在向内的拐点。这恰好就是矩形的一种定义。
首先 $t_1$ 显然满足 $\geq 1$，所以要满足 $t_1=1,t_2=0$ 只需要记录 $t_1+t_2$ 并计算其 $=1$ 的数量即可。
P2 计算初值
先解决如何计算初值。
考虑不断把 $i$ 指针往后移动并把 $i$ 染成黑色，则 $i$ 可以理解为一个时间点。
设 $v_i$ 表示前 $i$ 个时间点，满足 $t_1+t_2=1$ 的数量。
现在是第 $i$ 次操作，即需要把第 $i$ 个点染成黑色，先转移 $v_i = v_{i-1}$。
先计算第 $i$ 个点本身的贡献：
- 若左、上方都 $\gt i$，表示它们此时都是白点，$v_i \leftarrow v_i+1$。
- 这个可以通过编号最小值与 $i$ 比较得到。
- 若 $\gt i$ 则表示都是白点。
- 若四联通位置有 $\geq 2$ 个黑点，则这个点被染黑之前有 $+1$ 的贡献，但现在染黑了，所以要 $v_i \leftarrow v_i-1$。
- 这一操作可以通过记录编号次小值与 $i$ 比较得到。
- 若 $\lt i$ 则表示有 $\geq 2$ 个黑点。
然后考虑 $i$ 对周围点的贡献，设周围点的坐标是 $(x,y)$：
- 若 $(x,y)$ 左、上编号最小值 $=i$，且 $(x,y)$ 现在是黑点，则 $i$ 之前对 $(x,y)$ 有 $+1$ 的贡献，现在要 $v_i \leftarrow v_i-1$。
- 若 $(x,y)$ 四联通编号次小值 $=i$，且 $(x,y)$ 现在是白点，则 $i$ 之前没有对 $(x,y)$ 产生贡献，现在要加上，即 $v_i \leftarrow v_i+1$。
- 记得判定 $(x,y)$ 不要越界。
P3 支持修改
题目中一个很烦的事情就是要支持交换两个元素。
之前提到如果维护前缀最大最小值是无法快速修改的，但新的这种判定方法相对而言就比较简单且高效。
交换两个元素的时候需要用类似计算初值的方法，找出所有相邻元素，先把之前的贡献减掉，再交换两个元素，并加上新的贡献。
P4 数据结构
考虑用一个数据结构维护这个修改和查询过程。
它需要支持查询区间 $1$ 的个数，支持区间加。
这显然是线段树可以维护的东西，维护区间 $1$ 的个数可以转化为维护区间最小值和最小值出现次数（因为最小也只能是 $1$，不可能有 $\leq 0$）。
区间查询个数的套路在之前的几题也有出现过多次。
所以用线段树摁维护这个过程完事了。
P5 实现细节
- $u > v$ 会炸！！
- 修改的时候把四联通拉出来拿的是编号，不是下标！！！
swap的时候下标不要写错啊啊啊！！！- 离散化后有
tot个，而不是idx！！！！！ - 线段树查询要先特判最小值是否为 1！！！
- 你明明把所有下标都
+1了为什么询问的时候没有+1？？？ - 给我把题解写完再写代码，不然大于小于号写反的 bug 会满天飞。
- 修改的时候要判 $l>r$ 的情况，而且是左闭右开！！！！！
这个人写一份代码出了至少八个错，警钟敲烂。
而且上述八个 bug 只修了两三个，还能获得优秀的 20pts。
P6 代码
/*
2024.11.10
by Conan15
题解：https://www.acwing.com/solution/content/257793/
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 15;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1}; //上、左、下、右
int h, w, s, q;
int posx[N], posy[N]; //编号对应现在的位置
int id[N]; //下标对应是什么人
int t[N]; //[1,i] 的 t1+t2
int get_id(int x, int y) { //(x,y) 对应的下标
return (x - 1) * w + y;
}
int black(int x, int y) { //判定黑点是否有贡献：左、上是否均为白点，通过 id 最小值判定
int Min = 0x3f3f3f3f;
for (int i = 0; i < 2; i++) {
//上、左
int xx = x + dx[i], yy = y + dy[i];
if (xx < 1 || xx > h || yy < 1 || yy > w) continue;
Min = min(Min, id[get_id(xx, yy)]);
}
return Min; //最小值
}
int white(int x, int y) { //判定白点是否有贡献：四联通是否有 >=2 个黑点，通过 id 次小值判定
int Min = 0x3f3f3f3f, Se = 0x3f3f3f3f;
for (int i = 0; i < 4; i++) {
int xx = x + dx[i], yy = y + dy[i];
if (xx < 1 || xx > h || yy < 1 || yy > w) continue;
int res = id[get_id(xx, yy)];
if (res <= Min) Se = Min, Min = res;
else if (res < Se) Se = res;
}
return Se; //次小值
}
//--------------- Segment Tree ---------------
struct Tree {
int l, r;
int Min, cnt;
int flag;
} tr[N << 2];
void pushup(int u) {
tr[u].Min = min(tr[u << 1].Min, tr[u << 1 | 1].Min);
tr[u].cnt = 0;
if (tr[u].Min == tr[u << 1].Min) tr[u].cnt += tr[u << 1].cnt;
if (tr[u].Min == tr[u << 1 | 1].Min) tr[u].cnt += tr[u << 1 | 1].cnt;
}
void pushdown(int u) {
if (tr[u].flag) {
tr[u << 1].flag += tr[u].flag;
tr[u << 1 | 1].flag += tr[u].flag;
tr[u << 1].Min += tr[u].flag;
tr[u << 1 | 1].Min += tr[u].flag;
tr[u].flag = 0;
}
}
void build(int u, int l, int r) {
tr[u].l = l, tr[u].r = r;
tr[u].flag = 0;
if (l == r) {
tr[u].Min = t[l];
tr[u].cnt = 1;
return;
}
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
void change(int u, int l, int r, int d) {
if (l > r) return;
if (tr[u].r < l || tr[u].l > r) return;
if (tr[u].l >= l && tr[u].r <= r) {
tr[u].Min += d;
tr[u].flag += d;
return;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) change(u << 1, l, r, d);
if (r > mid) change(u << 1 | 1, l, r, d);
pushup(u);
}
int query() {
if (tr[1].Min != 1) return 0;
return tr[1].cnt;
}
//--------------- Segment Tree ---------------
void init() {
for (int i = 1; i <= s; i++) {
t[i] = t[i - 1];
int x = posx[i], y = posy[i];
if (black(x, y) > i) t[i]++;
if (white(x, y) < i) t[i]--;
for (int k = 0; k < 4; k++) {
int xx = x + dx[k], yy = y + dy[k];
if (xx < 1 || xx > h || yy < 1 || yy > w) continue;
if (black(xx, yy) == i && id[get_id(xx, yy)] < i) t[i]--;
if (white(xx, yy) == i && id[get_id(xx, yy)] > i) t[i]++;
}
}
build(1, 1, s);
}
int p[30], idx = 0, tot = 0; //离散化
int main() {
scanf("%d%d%d", &h, &w, &q);
s = h * w;
for (int i = 1, x, y; i <= s; i++) {
scanf("%d%d", &x, &y);
x++, y++;
posx[i] = x, posy[i] = y;
id[get_id(x, y)] = i;
}
init();
for (int C = 1; C <= q; C++) {
int u, v; scanf("%d%d", &u, &v);
u++, v++;
if (v < u) swap(u, v); //令 u < v
idx = 0;
for (int i = 0; i < 4; i++) {
int x = posx[u] + dx[i], y = posy[u] + dy[i];
if (x < 1 || x > h || y < 1 || y > w) continue;
p[++idx] = id[get_id(x, y)]; //是 id[get()]，不是 get()
}
for (int i = 0; i < 4; i++) {
int x = posx[v] + dx[i], y = posy[v] + dy[i];
if (x < 1 || x > h || y < 1 || y > w) continue;
p[++idx] = id[get_id(x, y)]; //同上
}
p[++idx] = u, p[++idx] = v; //自己本身也要修改
sort(p + 1, p + 1 + idx);
tot = unique(p + 1, p + 1 + idx) - p - 1;
for (int i = 1; i <= tot; i++) {
int x = posx[p[i]], y = posy[p[i]];
int blk = black(x, y), wht = white(x, y);
if (blk > p[i]) {
int l = max(u, p[i]), r = min(v, blk);
change(1, l, r - 1, -1);
}
if (wht < p[i]) {
int l = max(u, wht), r = min(v, p[i]);
change(1, l, r - 1, -1);
}
}
swap(id[get_id(posx[u], posy[u])], id[get_id(posx[v], posy[v])]); //注意不是 swap(id[u], id[v])
swap(posx[u], posx[v]), swap(posy[u], posy[v]);
for (int i = 1; i <= tot; i++) { //是 tot 不是 idx！！
int x = posx[p[i]], y = posy[p[i]];
int blk = black(x, y), wht = white(x, y);
if (blk > p[i]) {
int l = max(u, p[i]), r = min(v, blk);
change(1, l, r - 1, 1);
}
if (wht < p[i]) {
int l = max(u, wht), r = min(v, p[i]);
change(1, l, r - 1, 1);
}
}
printf("%d\n", query());
}
return 0;
}
你咋这么牛
%%%