题解：CF1840E Character Blocking

这样定义数组

a

：若

i

没被封锁，

a_i = [s1_i \ne t1_i]

，否则

a_i = 0

。

先摆结论。一次操作只有

O(1)

个位置的

a

值可能被改变。证明：

对于 $i$ 时刻的一次封锁，可能会改变 $a_{pos1}$ ；在 $i + t$ 时刻解锁也会改变它。
对于一次交换，只可能改变 $a_{pos1}$ 和 $a_{pos2}$ 。

查询就求

a

是否全零。动态维护

cnt

表示

1

的个数即可。

CPP

#include<bits/stdc++.h>
using namespace std;
int main() {
	int T;
	cin >> T;
	using vi = vector<int>;
	using vvi = vector<vi>;
	using ull = unsigned long long;
	mt19937_64 rnd(time(0));
	vector<ull> rd(200001);
	for (int i = 0; i <= 200000; i++) rd[i] = rnd();
	while (T--) {
		string s1, s2;
		cin >> s1 >> s2;
		int t, q, n = s1.size();
		cin >> t >> q;
		vvi ubl(q + 1);
		ull h = 0;
		for (int i = 0; i < n; i++) {
			if (s1[i] != s2[i]) {
				h ^= rd[i];
			}
		}
		auto upd = [&](int pos) {
			if (s1[pos] != s2[pos]) {
				h ^= rd[pos];
			}
		};
		for (int i = 1; i <= q; i++) {
			int opt;
			cin >> opt;
			for (int pos : ubl[i]) {
				upd(pos);
			}
			if (opt == 1) {
				int pos;
				cin >> pos;
				pos--;
				upd(pos);
				if (i + t <= q) ubl[i + t].push_back(pos);
			}
			if (opt == 2) {
				int num1, pos1, num2, pos2;
				cin >> num1 >> pos1 >> num2 >> pos2;
				pos1--;
				pos2--;
				upd(pos1);
				upd(pos2);
				if (num1 == 1 && num2 == 1) {
					swap(s1[pos1], s1[pos2]);
				}
				if (num1 == 1 && num2 == 2) {
					swap(s1[pos1], s2[pos2]);
				}
				if (num1 == 2 && num2 == 1) {
					swap(s2[pos1], s1[pos2]);
				}
				if (num1 == 2 && num2 == 2) {
					swap(s2[pos1], s2[pos2]);
				}
				upd(pos1);
				upd(pos2);
			}
			if (opt == 3) {
				if (h == 0) {
					cout << "YES\n";
				} else {
					cout << "NO\n";
				}
			}
		}
	}
}

题解：CF1840E Character Blocking

文章操作

相关推荐

评论

题解：CF1840E Character Blocking