Statement
给你两个字符串。
操作有:
- 忽视两个字符串的同一位置一段时间。
- 交换某两个未被忽视的字符(可以跨越字符串)。
- 查询字符串未被忽视的部分是否相等。
Solution
考虑字符串哈希。
对每个字符设置一个 hash 值 \(\mathrm{ref}\),对每个位置设置一个 hash 值 \(\mathrm{base}\)。
字符串的 hash 值为 \(\sum_{i=0}^{len} ( \mathrm{ref}_{s_i} \cdot \mathrm{base}_i)\)。
操作一即钦定 \(s_1\) 的某一位置等于 \(s_0\),开一个队列维护这个操作,到了一定时间就撤销即可。
操作二即模拟 hash 值的变化,见代码。
操作三即判断 hash 值是否相等。
单个测试点时间复杂度 \(\mathcal{O}(q)\)。
Code
#include <bits/stdc++.h>
using i64 = long long;
const i64 mask = (1 << 20) - 1;
void solve() {
std::mt19937 rnd(time(0));
std::vector<i64> ref(26);
for (i64& i : ref) i = (rnd() & mask);
std::string s[2];
std::cin >> s[0] >> s[1];
std::vector<i64> base(s[0].size());
for (i64& i : base) i = rnd() & mask;
i64 hash[2] = {0, 0};
auto hash_char = [&ref](const char ch) { return ref[ch - 'a']; };
auto get_hash = [&hash_char, &ref, &base](std::string s, i64& v) {
v = 0;
for (int i = 0; i < (int)s.size(); ++i) v += hash_char(s[i]) * base[i];
};
get_hash(s[0], hash[0]);
get_hash(s[1], hash[1]);
int q, t;
std::cin >> t >> q;
std::queue<std::pair<i64, int>> queue;
for (int i = 0; i < q; ++i) {
if (queue.size()) {
auto x = queue.front();
if (x.second == i) {
queue.pop();
hash[1] -= x.first;
}
}
int opt;
std::cin >> opt;
if (opt == 1) {
int pos;
std::cin >> pos;
--pos;
hash[1] += (hash_char(s[0][pos]) - hash_char(s[1][pos])) * base[pos];
queue.push({(hash_char(s[0][pos]) - hash_char(s[1][pos])) * base[pos], i + t});
} else if (opt == 2) {
int is[2], pos[2];
std::cin >> is[0] >> pos[0] >> is[1] >> pos[1];
--is[0], --is[1], --pos[0], --pos[1];
hash[is[0]] +=
(hash_char(s[is[1]][pos[1]]) - hash_char(s[is[0]][pos[0]])) * base[pos[0]];
hash[is[1]] +=
(hash_char(s[is[0]][pos[0]]) - hash_char(s[is[1]][pos[1]])) * base[pos[1]];
std::swap(s[is[0]][pos[0]], s[is[1]][pos[1]]);
} else {
if (hash[0] == hash[1])
std::cout << "YES" << '\n';
else
std::cout << "NO" << '\n';
}
}
}
int main() {
int tt;
std::cin >> tt;
while (tt--) solve();
return 0;
}