题解：CF1881G Anya and the Mysterious String

题意

给定一个字符串，有两种操作：

1 l r x 表示将区间内的字符整体循环右移位；
2 l r 判断区间内是否包含长度大于 1 的回文子串。

思路

如果我们直接判断是否包含回文子串，那么比较不好做。我们先来观察性质，题目并没有要求求出长度，所以我们挑最好求的来做。长度大于 1 的回文串都可以缩成 2 种：长度为 2 或 3 的回文串。下面来分类讨论：

长度为 2 的回文串，出现的条件是字符和字符相等；
长度为 3 的回文串，出现的条件是字符和字符相等。

于是，我们可以先处理出长度为 2 和 3 的回文串的左端点（右端点一样）。判定条件有了，现在考虑如何处理查询。区间整体加一个值，区间内该相等的还是相等，该不相等的依然不相等。所以，区间内的信息并没有变化。我们只需考虑区间端点左右的信息。

先考虑长度为 2 的回文串的变化。每次区间加数值，只需考虑和即可，如果这两个相等，就将答案加进容器中，如果不相等且原来相等（即原来出现在容器内）就将其删去。

在考虑长度为 3 的回文串的变化。需要考虑和。按照上面的方法更新即可。

区间信息维护，可以使用线段树。

代码

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;

const int MAXN = 2e5 + 10;

int n, m;
string s;

struct Node {
  ll sum, len;
};

struct Tag {
  ll val;
  bool operator==(const Tag &oth) const {
    return val == oth.val;
  }
};

struct SegTree {
  Node dat[MAXN << 2], E = {0, 0};
  Tag tag[MAXN << 2], I = {0};
  Node comb(const Node &dat1, const Node &dat2) {
    return {dat1.sum + dat2.sum, dat1.len + dat2.len};
  }
  Tag F(const Tag &tag1, const Tag &tag2) {
    return {tag1.val + tag2.val};
  }
  Node f(const Node &dat, const Tag &tag) {
    return {dat.sum + dat.len * tag.val, dat.len};
  }
  void down(int root) {
    if (tag[root] == I) return;
    tag[root << 1] = F(tag[root << 1], tag[root]);
    tag[root << 1 | 1] = F(tag[root << 1 | 1], tag[root]);
    dat[root << 1] = f(dat[root << 1], tag[root]);
    dat[root << 1 | 1] = f(dat[root << 1 | 1], tag[root]);
    tag[root] = I;
  }
  void build(int root, int l, int r) {
    tag[root] = I;
    if (l == r) {
      dat[root] = {s[l] - 'a', 1};
      return;
    }
    int mid = l + r >> 1;
    build(root << 1, l, mid);
    build(root << 1 | 1, mid + 1, r);
    dat[root] = comb(dat[root << 1], dat[root << 1 | 1]);
  }
  void modify(int root, int l, int r, int L, int R, Tag t) {
    if (L <= l && R >= r) {
      dat[root] = f(dat[root], t);
      tag[root] = F(tag[root], t);
      return;
    }
    down(root);
    int mid = l + r >> 1;
    if (L <= mid) modify(root << 1, l, mid, L, R, t);
    if (R > mid) modify(root << 1 | 1, mid + 1, r, L, R, t);
    dat[root] = comb(dat[root << 1], dat[root << 1 | 1]);
  }
  Node query(int root, int l, int r, int pos) {
    if (l == r) return dat[root];
    down(root);
    int mid = l + r >> 1;
    return pos <= mid ? query(root << 1, l, mid, pos) : query(root << 1 | 1, mid + 1, r, pos);
  }
} T;

void Solve() {
  cin >> n >> m >> s;
  s = '#' + s;
  set<int> s2, s3;
  for (int i = 1; i < n; i++) {
    if (s[i] == s[i + 1]) {
      s2.insert(i);
    }
  }
  for (int i = 1; i < n - 1; i++) {
    if (s[i] == s[i + 2]) {
      s3.insert(i);
    }
  }
  T.build(1, 1, n);
  for (int op, l, r, x; m--; ) {
    cin >> op >> l >> r;
    if (op == 1) {
      cin >> x;
      T.modify(1, 1, n, l, r, {x});
      int p = T.query(1, 1, n, l - 1).sum % 26, q = T.query(1, 1, n, l).sum % 26;
      if (p == q) s2.insert(l - 1);
      else {
        if (s2.count(l - 1)) s2.erase(l - 1);
      }
      p = T.query(1, 1, n, r).sum % 26, q = T.query(1, 1, n, r + 1).sum % 26;
      if (p == q) s2.insert(r);
      else {
        if (s2.count(r)) s2.erase(r);
      }
      for (int k = l - 1; k >= max(0, l - 2); k--) {
        if (k + 2 > n) continue;
        int u = T.query(1, 1, n, k).sum % 26, v = T.query(1, 1, n, k + 2).sum % 26;
        if (u == v) s3.insert(k);
        else {
          if (s3.count(k)) s3.erase(k);
        }
      }
      for (int k = r - 1; k <= r; k++) {
        if (k < 1) continue;
        int u = T.query(1, 1, n, k).sum % 26, v = T.query(1, 1, n, k + 2).sum % 26;
        if (u == v) s3.insert(k);
        else {
          if (s3.count(k)) s3.erase(k);
        }
      }
    } else {
      auto it = s2.lower_bound(l);
      if (it != s2.end() && (*it) + 1 <= r) {
        cout << "NO\n";
        continue;
      }
      it = s3.lower_bound(l);
      if (it != s3.end() && (*it) + 2 <= r) {
        cout << "NO\n";
        continue;
      }
      cout << "YES\n";
    }
  }
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  int _T;
  for (cin >> _T; _T--; Solve());
  return 0;
}