前言
题目链接:洛谷。
时间复杂度和输入同阶的做法。
题意简述
有 \(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;
}
标签:const,POI2008,int,题解,tree,tot,fa,Trains,集合
From: https://www.cnblogs.com/XuYueming/p/18332502