题解：CF1840E Character Blocking

anll · 2025-09-26 21:16:41 · 题解

这样定义数组 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 的个数即可。

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