[Q] F - Palindrome Query

考察
0. 回文を高速に判定する技あるかな？何も思いつかない。トリッキーな工夫の余地がないように見える。

ものすごく単純に「文字列Sの切り出しと、逆さ文字列Tの切り出しが同一か比較する」を回答する。この方法を軸に高速化できないか考える。

int main() {
  ll N, Q;
  string S, T;
  cin >> N >> Q >> S;
  T = S;
  reverse(all(T));
  ll q, x, L, R;
  char c;
  while(Q--){
    cin >> q;
    if (q == 1){
      cin >> x >> c;
      --x;
      S[x] = c;
      T[N - x - 1] = c;
    }
    else{
      cin >> L >> R;
      --L; --R;
      // 文字列の切り出しと、逆さ文字列の切り出しが同一か比較する
      string s = S.substr(L, R - L + 1);
      string t = T.substr(N - R - 1, R - L + 1);
      if (s == t){
        cout << "Yes" << endl;
      }
      else{
        cout << "No" << endl;
      }
    }
  }
}

解説を見ると、クエリ2がきたときに、回文かどうかの判定を1文字ずつ比較しないようだ。文字列を数値として扱い、O(1)で判定できるらしい。RollingHashという。ロリハしていこうと思う。

1. 文字列Sに対して、逆さにした文字列Tを用意する。
2. 文字列をhash化する。

S = "a b c"とすると、
     a = 'a' * 2^0
       b = 'b' * 2^1
         c = 'c' * 2^2
といったように、indexによって次元を分けて、BITに格納する。

このとき、文字列とhashの対応は累積和をとればよくて
memo["abc"] = 'a' * 2^0 + 'b' * 2^1 + 'c' * 2^2
memo["ac"] = 'a' * 2^0 + 'c' * 2^2
のような対応になる。

Q. 文字がずれている場合は？
S="abac"
T="caba"
とあった場合。abaで回文判定をしたい。

このとき、Tで得られた"aba"のhashを<<1すれば、Sで得られた"aba"のhashと一致する。

A. 累積和なので、全部の値をbaseでかけたり割ったりすれば、補正できる。

3. クエリ1がきたときに文字を変更する。このときhashは高速に再計算できる必要がある。BITで管理し、累積和を求めるようにしてhashを生成すればよさそう。遅延セグ木でも可能だと思う。

4. 正確性が問題になる。Hashの衝突をさけるには、どれくらい値に余裕が必要？
MODに対してroot(MOD)くらいの値までなら、衝突をほぼ避けられるらしい。
リスクを下げるために2つのバリエーションをもたせる必要がある。素数となるMODと、baseの2種類だ。

N=1e6なので、MOD=1e12をとりたい。
しかし、計算過程で掛け算が生じるので、longlongでオーバーフローしないように、MOD=1e9程度におさえたい。
MOD=1e9を2パターン計算し、MOD^2=1e18ほどの精度に上げる方法をとる。

バリエーションについて、MODだけだと十分ではないので注意。baseも変動させる必要がある。
[ref] baseを2に固定した場合、1WA。
https://atcoder.jp/contests/abc331/submissions/48169446

そもそもの話、RollingHashは完全に安全な回答ではないようだ。

5. MODとbaseを変更した2パターンでsolve()を行い、いずれでも回文と判定できたものについて"Yes"として扱えば盤石になりそう

実装

/////////////////////////// Bit
template <ll BT>
struct Bit {
  mint dat[BT + 10]{};
  void add(ll i, mint x) {
    ++i;
    for (; i < BT; i += i & -i) dat[i] += x;
  }
  mint sum(ll i) {  // [0, i]
    if (i < 0) return 0;
    if (i >= BT - 1) i = BT - 2;
    ++i;
    mint res = 0;
    for (; i > 0; i -= i & -i) res += dat[i];
    return res;
  }
  mint rangesum(ll L, ll R) {  // [L, R]
    return sum(R) - sum(L - 1);
  }
};

/////////////////////////// Main
Bit<1000010> bit[4];
vector<mint> pows(1000010, 1);
int main() {
  cincout();
  ll N, Q;
  string S, T;
  cin >> N >> Q >> S;
  T = S;
  reverse(all(T));
  vector<tll> query;

  rep(q, Q) {
    ll a, x, L, R;
    char c;
    cin >> a;
    if (a == 1) {
      cin >> x >> c;
      query.emplace_back(a, x, c);
    } else {
      cin >> L >> R;
      query.emplace_back(a, L, R);
    }
  }

  // 2種類のMODとbaseで回文の判定をする。両方がtrueの場合にYes
  vector<bool> ans(Q, true);
  auto solve = [&](ll mod, ll p, Bit<1000010>& bit0, Bit<1000010>& bit1, string S,
                   string T) {
    // MODとbaseの設定
    MOD = mod;
    rep(i, N) pows[i + 1] = pows[i] * p;
    rep(i, N) {
      mint s = S[i] - 'a';
      mint t = T[i] - 'a';
      bit0.add(i, s * pows[i]);
      bit1.add(i, t * pows[i]);
    }
    // query処理
    rep(q, Q) {
      auto [a, b, _c] = query[q];
      if (a == 1) {
        ll x = b - 1;
        char c = _c;
        mint s = S[x] - 'a';
        mint t = T[N - x - 1] - 'a';
        bit0.add(x, -s * pows[x]);
        bit1.add(N - x - 1, -t * pows[N - x - 1]);
        S[x] = c;
        T[N - x - 1] = c;
        s = c - 'a';
        t = c - 'a';

        bit0.add(x, s * pows[x]);
        bit1.add(N - x - 1, t * pows[N - x - 1]);
      } else {
        ll L = b, R = _c;
        --L, --R;
        mint s = bit0.rangesum(L, R);
        mint t = bit1.rangesum(N - R - 1, N - L - 1);
        // 補正
        if (N - R - 1 > L) {
          s *= pows[(N - R - 1) - L];
        } else {
          t *= pows[L - (N - R - 1)];
        }
        ans[q] = (s == t) & ans[q];
      }
    }
  };
  // 2種類のMODとbase
  solve(1212121217, rand() % 1212121217, bit[0], bit[1], S, T);
  solve(1212121219, rand() % 1212121219, bit[2], bit[3], S, T);
  rep(q, Q) {
    auto [a, b, c] = query[q];
    if (a == 1) continue;
    if (a == 2) {
      if (ans[q])
        cout << "Yes" << endl;
      else
        cout << "No" << endl;
    }
  }
}

https://atcoder.jp/contests/abc331/submissions/48172490