526互联

Solution to CF1840E Character Blocking

发布时间 2023-07-24 18:17:58作者: escap1st

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;
}