题解
考虑求连通块个数可以用并查集，区间询问可以用线段树。把他们丢在一起做即可。
具体地，线段树每个结点维护对应区间的连通块个数、对应区间最左边的一列、对应区间最右边的一列。
线段树合并信息的时候就是对相邻两列用并查集合并。
如果并查集能合并，那么连通块个数减一。
#include <cstdio>
#include <cctype>
#include <cstring>
#define MAX_N (10 + 5)
#define MAX_M (100000 + 5)
int n, m, q;
int a[MAX_N][MAX_M];
int rt[MAX_N * MAX_M], tot;
struct Node {
int cnt, l[MAX_N], r[MAX_N];
} s[MAX_M << 2], ans;
void Read(int &x) {
x = 0;
char ch = getchar();
while (!isdigit(ch)) ch = getchar();
while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
}
void Write(int x) {
if (x >= 10) Write(x / 10);
putchar(x % 10 + '0');
}
int Root(int x) {
if (rt[x] == x) return x;
return rt[x] = Root(rt[x]);
}
void Merge(Node &S, Node L, Node R, int mid) {
S.cnt = L.cnt + R.cnt;
memcpy(S.l, L.l, sizeof S.l);
memcpy(S.r, R.r, sizeof S.r);
for (int i = 1; i <= n; ++i) {
rt[L.l[i]] = L.l[i];
rt[L.r[i]] = L.r[i];
rt[R.l[i]] = R.l[i];
rt[R.r[i]] = R.r[i];
}
for (int i = 1; i <= n; ++i)
if (a[i][mid] == a[i][mid + 1] && Root(L.r[i]) != Root(R.l[i]))
rt[Root(L.r[i])] = Root(R.l[i]), --S.cnt;
for (int i = 1; i <= n; ++i) S.l[i] = Root(S.l[i]), S.r[i] = Root(S.r[i]);
}
void Build(int x, int l, int r) {
if (l == r) {
for (int i = 1; i <= n; ++i) {
if (a[i][l] == a[i - 1][l]) s[x].l[i] = s[x].l[i - 1];
else s[x].l[i] = ++tot, ++s[x].cnt;
s[x].r[i] = s[x].l[i];
}
return;
}
int mid = l + r >> 1;
Build(x << 1, l, mid);
Build(x << 1 | 1, mid + 1, r);
Merge(s[x], s[x << 1], s[x << 1 | 1], mid);
}
void Query(int x, int l, int r, int L, int R) {
if (R < l || r < L) return;
if (L <= l && r <= R) {
if (!ans.cnt) ans = s[x];
else Merge(ans, ans, s[x], l - 1);
return;
}
int mid = l + r >> 1;
Query(x << 1, l, mid, L, R);
Query(x << 1 | 1, mid + 1, r, L, R);
}
int main() {
Read(n), Read(m), Read(q);
for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) Read(a[i][j]);
Build(1, 1, m);
int l, r;
while (q--) {
Read(l), Read(r);
ans.cnt = 0;
memset(ans.l, 0, sizeof ans.l);
memset(ans.r, 0, sizeof ans.r);
Query(1, 1, m, l, r);
Write(ans.cnt), putchar('
');
}
return 0;
}