思路
线段树。
题意可以转化成每次判定有多少个前缀满足所有结点构成矩形。
首先排除确定矩阵坐标再数答案的做法，因为太难。
所以考虑如何对前缀进行判定。
一个简单的想法是维护前 \(i\) 个点中 \(x, y\) 坐标的最值，但这样只能暴力看矩阵中的所有元素，跑得很慢。
不妨思考一下合法的条件：
-
前 \(i\) 个点都可以被一个矩形覆盖，这个恒成立。
-
这个矩形内没有其他的点。
对于 2，考虑把前 \(i\) 个点和剩下的点分开，考虑把前 \(i\) 个染成黑色，后面的染成白色。
于是现在可以考虑黑白分布情况：
-
所有的黑点必须连通，等价于左边的相邻点和上边的相邻点都是白点的黑点只有 \(1\) 个。
-
矩形内没有白点，也就是说黑点不会有 L 形的分布，等价于不存在相邻点中有超过一个黑点的白点。
结论不会证，但是是对的，差点猜出来。
不太好维护每个时刻图内的状况。
换个角度，既然每次交换至多影响 \(10\) 个点的状态，那直接维护每个点对答案的贡献，每次只需要 \(O(\log)\) 计算贡献就能做。
先考虑第一个条件。如果点 \((x, y)\) 在时刻 \(i\) 是合法的，那么显然有 \(t_{x, y} \leq i < \min(t_{x - 1, y}, t_{x, y - 1})\).
第二个条件同理有 \(\operatorname{SecondMin(t_{x - 1, y}, t_{x, y - 1}, t_{x + 1, y}, t_{x, y + 1})} \leq i < t_{x, y}\).
于是一个点可以贡献的时刻都是确定的，直接对于点动态算贡献就好了。
注意四连通的点处理出来之后要去重，不然就会喜提 56pts.
代码
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> pii;
#define il inline
#define fi first
#define se second
#define mp make_pair
const int maxn = 1e6 + 5;
const int sgt_sz = maxn << 2;
const int inf = 2e9;
int h, w, q, n;
int tmp[4];
int r[maxn], c[maxn];
int dx[5] = {0, -1, 1, 0, 0}, dy[5] = {0, 0, 0, -1, 1};
pii que[10];
vector<int> a[maxn];
il int read()
{
int res = 0;
char ch = getchar();
while ((ch < '0') || (ch > '9')) ch = getchar();
while ((ch >= '0') && (ch <= '9')) res = res * 10 + ch - '0', ch = getchar();
return res;
}
il void write(int x)
{
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
il void write(int x, char ch) { write(x), putchar(ch); }
namespace SGT
{
#define ls (k << 1)
#define rs (k << 1 | 1)
int lazy[sgt_sz];
struct node
{
int v[2], c[2];
node() { v[0] = v[1] = c[0] = c[1] = 0; }
friend node operator + (node a, node b)
{
node res;
res.v[0] = min(a.v[0], b.v[0]);
res.v[1] = min(max(a.v[0], b.v[0]), min(a.v[1], b.v[1]));
if (res.v[0] == res.v[1]) res.v[1] = inf;
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
{
if (res.v[i] == a.v[j]) res.c[i] += a.c[j];
if (res.v[i] == b.v[j]) res.c[i] += b.c[j];
}
return res;
}
} tr[sgt_sz];
il void push_up(int k) { tr[k] = tr[ls] + tr[rs]; }
il void push_down(int k)
{
tr[ls].v[0] += lazy[k], tr[ls].v[1] += lazy[k], lazy[ls] += lazy[k];
tr[rs].v[0] += lazy[k], tr[rs].v[1] += lazy[k], lazy[rs] += lazy[k];
lazy[k] = 0;
}
il void build(int k, int l, int r)
{
lazy[k] = 0, tr[k].v[1] = inf, tr[k].c[0] = r - l + 1;
if (l == r) return;
int mid = (l + r) >> 1;
build(ls, l, mid), build(rs, mid + 1, r);
}
il void update(int k, int l, int r, int ql, int qr, int w)
{
if (ql > qr) return;
if ((l >= ql) && (r <= qr)) return tr[k].v[0] += w, tr[k].v[1] += w, lazy[k] += w, void();
push_down(k);
int mid = (l + r) >> 1;
if (ql <= mid) update(ls, l, mid, ql, qr, w);
if (qr > mid) update(rs, mid + 1, r, ql, qr, w);
push_up(k);
}
il int query()
{
if (tr[1].v[0] == 1) return tr[1].c[0];
if (tr[1].v[1] == 1) return tr[1].c[1];
return 0;
}
}
using namespace SGT;
bool in(int x, int y) { return (x >= 1) && (x <= h) && (y >= 1) && (y <= w); }
int chk1(int x, int y)
{
int res = n + 1;
res = min(res, (x > 1 ? a[x - 1][y] : inf));
res = min(res, (y > 1 ? a[x][y - 1] : inf));
return res - 1;
}
int chk2(int x, int y)
{
tmp[0] = (x > 1 ? a[x - 1][y] : inf), tmp[1] = (x < h ? a[x + 1][y] : inf);
tmp[2] = (y > 1 ? a[x][y - 1] : inf), tmp[3] = (y < w ? a[x][y + 1] : inf);
sort(tmp, tmp + 4);
return tmp[1];
}
int main()
{
h = read(), w = read(), q = read(), n = h * w;
for (int i = 1; i <= h; i++) a[i].resize(w + 1);
for (int i = 1; i <= n; i++)
{
r[i] = read() + 1, c[i] = read() + 1;
a[r[i]][c[i]] = i;
}
build(1, 1, n);
for (int i = 1; i <= h; i++)
for (int j = 1; j <= w; j++)
update(1, 1, n, a[i][j], chk1(i, j), 1), update(1, 1, n, chk2(i, j), a[i][j] - 1, 1);
while (q--)
{
int u = read() + 1, v = read() + 1, len = 0;
for (int i = 0, x, y, tx, ty; i < 5; i++)
{
x = r[u], y = c[u], tx = x + dx[i], ty = y + dy[i];
if (in(tx, ty)) que[++len] = mp(tx, ty);
x = r[v], y = c[v], tx = x + dx[i], ty = y + dy[i];
if (in(tx, ty)) que[++len] = mp(tx, ty);
}
sort(que + 1, que + len + 1);
len = unique(que + 1, que + len + 1) - que - 1;
for (int i = 1, tx, ty; i <= len; i++)
{
tx = que[i].fi, ty = que[i].se;
update(1, 1, n, a[tx][ty], chk1(tx, ty), -1), update(1, 1, n, chk2(tx, ty), a[tx][ty] - 1, -1);
}
swap(r[u], r[v]), swap(c[u], c[v]), swap(a[r[u]][c[u]], a[r[v]][c[v]]);
for (int i = 1, tx, ty; i <= len; i++)
{
tx = que[i].fi, ty = que[i].se;
update(1, 1, n, a[tx][ty], chk1(tx, ty), 1), update(1, 1, n, chk2(tx, ty), a[tx][ty] - 1, 1);
}
write(query(), '\n');
}
return 0;
}