T0801 字符变换

#include <bits/stdc++.h>
using namespace std;

/*
字符变换：一次操作给相邻两个字符各加 1（模 26）。
考虑交错和 alt(x) = x1 - x2 + x3 - x4 + ...
  - 给相邻两个位置各加 1，alt 不变（一个 +1 一个 -1）。
  - 反过来，任何 alt 相同的两个串都能互相变换得到（差向量落在
    {e_i + e_{i+1}} 生成的模 26 子群里，而该子群正好是 alt = 0 的全部向量）。
所以 s、t 相似 <=> alt(s) ≡ alt(t) (mod 26)。
每次修改 s 的一个位置，只要更新 alt(s) 即可。
*/

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    string s, t;
    cin >> s >> t;

    auto altOf = [&](const string &w) {
        long long v = 0;
        for (int i = 0; i < n; i++) {
            int c = w[i] - 'a';
            if (i & 1) v -= c; else v += c;
        }
        return ((v % 26) + 26) % 26;
    };

    long long alt = altOf(s);
    long long altT = altOf(t);

    auto sign = [&](int i) { return (i & 1) ? -1 : 1; };

    cout << (alt == altT ? "yes" : "no") << "\n";
    for (int i = 0; i < q; i++) {
        int pos;
        char c;
        cin >> pos >> c;
        --pos;
        alt -= sign(pos) * (s[pos] - 'a');
        s[pos] = c;
        alt += sign(pos) * (s[pos] - 'a');
        alt = ((alt % 26) + 26) % 26;
        cout << (alt == altT ? "yes" : "no") << "\n";
    }
    return 0;
}