This problem is intended to be solved with an hashing algorithm called Rolling Hash. We already described rolling hash in the editorial of ABC274 Ex, so refer to it if you do not know it.

Firstly, in this problem you are given an element-wise update query of a string, so it is a bit difficult to use a standard data structure on strings. Instead, we consider how to store the information regarding palindromes on a segment tree. However, naively putting it onto a segment tree may lead to an explosion of computation complexity, so we try to store its hash instead.

For a length-\(M\) string \(T = T_1 T_2 \dots T_M\), we define hash functions \(H_1(T)\) and \(H_2(T)\) on \(T\) as follows.
(In the following expression, \(T_i\) is interpreted as an integer, such as its ASCII code. Also, \(p\) is a prime and \(x\) is an integer between \(0\) and \((p-1)\).)

\[ \begin{aligned} H_1(T) &= \left( \sum_{i=1}^M T_i x^{M - i} \right) \bmod p \\ H_2(T) &= \left( \sum_{i=1}^M T_i x^{i - 1} \right) \bmod p \\ \end{aligned} \]

Intuitively, \(H_1(T)\) is the hash of \(T\) from left to right, and \(H_2(T)\) is the hash of \(T\) from right to left.

Here, if \(T\) is a palindrome, then \(H_1(T) = H_2(T)\) holds. Also, if \(T\) is not a palindrome, then it is very likely that \(H_1(T) \neq H_2(T)\) (with a probability of about \(1 - (M-1) / p\)). By comparing the hash values, one can probabilistically determine if \(T\) is a palindrome.
(When \(p \simeq 10^9\) and \(M \simeq 10^6\), if you use only one pair \((p, x)\), the theoretical probability of failure is \(10^{-3}\), which is rather high; however, by picking four pairs of \((p, x)\), the probability can be lowered to about \(10^{-12}\).)

Also, for strings \(S\) and \(T\), if their hash values \(H_1(S), H_2(S), H_1(T)\), and \(H_2(T)\) are known, the hash values of the string \(S + T\) can be obtained as:

\[ \begin{aligned} H_1(S + T) &= H_1(S) \times x^{|T|} + H_1(T) \\ H_2(S + T) &= H_2(S) + x^{|S|} \times H_2(T).\\ \end{aligned} \]

Therefore, by storing values \((H_1(S), H_2(S), x^{|S|})\) corresponds to a string \(S\), such information is suitable in a segment tree, which also supports element-wise update of a string.

By implementing the algorithm so far, the problem can be solved in a total of \(\mathrm{O}(N + Q \log N)\) time, which is fast enough.

• Sample code (C++)

#include <array>
#include <ctime>
#include <iostream>
#include <random>
#include <string>
using namespace std;
#include "atcoder/segtree.hpp"

constexpr int B = 5;
int mod[B] = {998244353, 1000000007, 1000000009, 1000000021, 1000000033};
int base[B];
struct Hash {
  long long h1, h2, pw;
};
using T = array<Hash, B>;

T op(T lhs, T rhs) {
  T res;
  for (int i = 0; i < B; i++) {
    res[i].h1 = (lhs[i].h1 * rhs[i].pw + rhs[i].h1) % mod[i];
    res[i].h2 = (lhs[i].h2 + lhs[i].pw * rhs[i].h2) % mod[i];
    res[i].pw = lhs[i].pw * rhs[i].pw % mod[i];
  }
  return res;
}
T e() {
  T res;
  for (int i = 0; i < B; i++) res[i] = {0, 0, 1};
  return res;
}
using SegTree = atcoder::segtree<T, op, e>;

T gen(char c) {
  T res;
  for (int i = 0; i < B; i++) res[i].h1 = res[i].h2 = c, res[i].pw = base[i];
  return res;
}

int main() {
  mt19937_64 rng(time(0));
  for (int i = 0; i < B; i++) base[i] = rng() % mod[i];

  cin.tie(0)->sync_with_stdio(0);
  int N, Q;
  string S;
  cin >> N >> Q >> S;

  vector<T> init(N);
  for (int i = 0; i < N; i++) init[i] = gen(S[i]);
  SegTree seg{init};

  while (Q--) {
    int cmd;
    cin >> cmd;
    if (cmd == 1) {
      int x;
      char c;
      cin >> x >> c;
      --x;
      seg.set(x, gen(c));
    } else {
      int l, r;
      cin >> l >> r;
      --l;
      auto h = seg.prod(l, r);
      bool flag = true;
      for (int i = 0; i < B; i++) flag &= h[i].h1 == h[i].h2;
      cout << (flag ? "Yes" : "No") << endl;
    }
  }
}