思路

发现如果一个字符串中有长度大于等于 \(2\) 回文子串，必定有长度为 \(2\) 的回文子串或长度为 \(3\) 的回文子串，并且形如：aa 和 aba。

所以考虑用线段树这两种情况。维护一段区间的最左、次左、最右、次右的元素，同时用两个标记变量 \(f_1,f_2\) 分别表示这个区间中是否出现形如 aa 和 aba 的子串即可。

code

#include <bits/stdc++.h>
#define re register

using namespace std;

const int N = 2e5 + 10;
int T,n,q;
char s[N];

inline int read(){
    int r = 0,w = 1;
    char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-') w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        r = (r << 3) + (r << 1) + (c ^ 48);
        c = getchar();
    }
    return r * w;
}

struct seg{
    #define ls(u) (u << 1)
    #define rs(u) (u << 1 | 1)

    struct node{
        int l;
        int r;
        int tag;
        int lc[2];
        int rc[2];
        bool f[2];
    }tr[N << 2];

    inline int Add(int a,int b){
        return (a + b) % 26;
    }

    inline node merge(node a,node b){
        node res = {a.l,b.r,0,{a.lc[0],a.lc[1]},{b.rc[0],b.rc[1]},{a.f[0] | b.f[0],a.f[1] | b.f[1]}};
        if (!~res.lc[1]) res.lc[1] = b.lc[0];
        if (!~res.rc[1]) res.rc[1] = a.rc[0];
        if (~a.rc[0] && ~b.lc[0] && a.rc[0] == b.lc[0]) res.f[0] = true;
        if (~a.rc[1] && ~b.lc[0] && a.rc[1] == b.lc[0]) res.f[1] = true;
        if (~a.rc[0] && ~b.lc[1] && a.rc[0] == b.lc[1]) res.f[1] = true;
        return res;
    }

    inline void calc(int u,int k){
        for (re int i = 0;i <= 1;i++){
            if (~tr[u].lc[i]) tr[u].lc[i] = Add(tr[u].lc[i],k);
            if (~tr[u].rc[i]) tr[u].rc[i] = Add(tr[u].rc[i],k);
        }
        tr[u].tag = Add(tr[u].tag,k);
    }

    inline void pushup(int u){
        tr[u] = merge(tr[ls(u)],tr[rs(u)]);
    }

    inline void pushdown(int u){
        if (tr[u].tag){
            calc(ls(u),tr[u].tag);
            calc(rs(u),tr[u].tag);
            tr[u].tag = 0;
        }
    }

    inline void build(int u,int l,int r){
        tr[u] = {l,r,0,{-1,-1},{-1,-1},{false,false}};
        if (l == r){
            tr[u].lc[0] = tr[u].rc[0] = s[l] - 'a';
            return;
        }
        int mid = l + r >> 1;
        build(ls(u),l,mid);
        build(rs(u),mid + 1,r);
        pushup(u);
    }

    inline void modify(int u,int l,int r,int k){
        if (l <= tr[u].l && tr[u].r <= r){
            calc(u,k);
            return;
        }
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(ls(u),l,r,k);
        if (r > mid) modify(rs(u),l,r,k);
        pushup(u);
    }
    
    inline node query(int u,int l,int r){
        if (l <= tr[u].l && tr[u].r <= r) return tr[u];
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid && r > mid) return merge(query(ls(u),l,r),query(rs(u),l,r));
        if (l <= mid) return query(ls(u),l,r);
        if (r > mid) return query(rs(u),l,r);
    }

    #undef ls
    #undef rs
}tree;

inline void solve(){
    n = read();
    q = read();
    scanf("%s",s + 1);
    tree.build(1,1,n);
    while (q--){
        int op;
        op = read();
        if (op == 1){
            int l,r,x;
            l = read();
            r = read();
            x = read();
            tree.modify(1,l,r,x);
        }
        else{
            int l,r;
            l = read();
            r = read();
            auto res = tree.query(1,l,r);
            if (res.f[0] | res.f[1]) puts("NO");
            else puts("YES");
        }
    }
}

int main(){
    T = read();
    while (T--) solve();
    return 0;
}

最后：祝 CSP-2023 J2/S2 RP += inf。