前言
题目链接：洛谷。
时间复杂度和输入同阶的做法。
题意简述
有 \(n\)（\(n \leq 10^3\)）个长 \(m\) 的字符串，\(q\)（\(q \leq 10^5\)）次操作，交换两个字符串的两个字符。问每个字符串在所有时刻，最多有几个和它相等。
题目分析
套路做法
看到字符串相等，想到使用哈希。但是要支持修改，怎么办呢？上数据结构！当然不是，把哈希的结果看做一个数字，每次把某一位的值扣掉再加上就行了。即减去该位权值乘上原值，加上权值乘上修改后的值。
至于询问，每次操作后不可能 \(\Theta(n^2)\) 地弄。发现只会和当前修改的两个串有关，故 \(\Theta(n)\) 把这两个串的结果统计一遍。其他的串，维护一个 \(cur_i\) 表示当前 \(i\) 能和几个字符串相等。如果 \(i\) 和修改之前的串相等，就减去，如果和修改后的串相等了，再加上，最后和答案取个 \(\max\) 即可。
时间复杂度 \(\Theta(nm + nq)\)。可过此题。当然，可以优化。
优化做法
尝试从哈希角度分析。发现，一个字符串不断从一个相同哈希值得集合中，移动到另一个集合中，而答案就是这段时间内，该集合大小的最大值。如果考虑在删除的时候统计答案，就是在该元素加入集合后，该集合大小的最大值。
尝试把集合大小独立出来，看做单独的一个权值。这样就可以把删除这个操作去掉。即我们可以把元素扩展，额外附加它在加入集合时集合的大小，并不做删除，而是直接将集合大小减一。这样查询，就成了一个后缀最大值。
对于一条链，我们会扫过很多次，不妨从这里优化，即去除重复操作。想到，如果扫过了一个值，那下次不用再从原来的位置开始再扫一遍，而是，把当前扫过来的最值记下来，下次直接从这里开始扫就行了。很类似并查集的路径压缩。
时间复杂度呢？每条边只会被经过一遍，和 \(n + q\) 是同阶的。总的时间复杂度是 \(\Theta(nm + q)\) 的，非常快。
代码
naive code
代码。
优化
哈希值域太小会 WA，所以使用了 unordered_map，对时间复杂度没有影响。略去了快读，是最优解。
#include <cstdio>
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
const int N = 1010;
const int M = 110;
const int Q = 100010;
const int mod = 1e9 + 11;
const int bas = 1331;
inline int add(int a, int b) {
return a + b >= mod ? a + b - mod : a + b;
}
inline int sub(int a, int b) {
return a - b < 0 ? a - b + mod : a - b;
}
inline int mul(int a, int b) {
return 1ll * a * b % mod;
}
int n, m, q;
char str[N][M];
int hsh[N], res[N], pw[M];
int whr[N];
struct node {
int fa, ans;
} tree[N + Q * 2];
int tot;
unordered_map<int, int> ysiz, ylst;
int query(int x) {
if (tree[x].fa == x) return tree[x].ans;
int res = query(tree[x].fa);
tree[x].fa = tree[tree[x].fa].fa;
return tree[x].ans = max(tree[x].ans, res);
}
void update(int x) {
int bl = hsh[x];
whr[x] = ++tot, ++ysiz[bl];
tree[tot] = {tot, ysiz[bl]};
tree[ylst[bl]].fa = tot;
ylst[bl] = tot;
}
signed main() {
fread(buf, 1, MAX, stdin);
read(n), read(m), read(q);
pw[0] = 1;
for (int i = 1; i <= m; ++i)
pw[i] = mul(pw[i - 1], bas);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
hsh[i] = add(mul(hsh[i], bas), str[i][j] = readchar());
}
update(i);
}
for (int i = 1, a, x, b, y; i <= q; ++i) {
read(a), read(x), read(b), read(y);
res[a] = max(res[a], query(whr[a])), --ysiz[hsh[a]];
if (a != b) res[b] = max(res[b], query(whr[b])), --ysiz[hsh[b]];
hsh[a] = sub(hsh[a], mul(pw[m - x], str[a][x]));
hsh[b] = sub(hsh[b], mul(pw[m - y], str[b][y]));
swap(str[a][x], str[b][y]);
hsh[a] = add(hsh[a], mul(pw[m - x], str[a][x]));
hsh[b] = add(hsh[b], mul(pw[m - y], str[b][y]));
update(a);
if (a != b) update(b);
}
for (int i = 1; i <= n; ++i) {
printf("%d\n", max(res[i], query(whr[i])));
}
return 0;
}