[Codefoces] G. Anya and the Mysterious String

Problem Link    : G. Anya and the Mysterious String
Category        : Approximate Problem
Contest         : Codeforces Round 903 (Div. 3) 

    #include "bits/stdc++.h"
    using namespace std;
    #define int     long long int
    #define endl    '\n'
 
    const int maxn = 2e5 + 5;
    const int chars = 26;
    const int INF = 1e9;
 
    struct Node {
        int value;
        int nxtsame;
        int lazy;
 
        Node(int value = 0, int nxtsame = INF, int lazy = 0)
            : value(value), nxtsame(nxtsame), lazy(lazy) {}
 
        void assignLeaf(int val) {
            value = val;
            nxtsame = INF;
            lazy = 0;
        }
        void assignLeafNxtsame(int nxt) {
            nxtsame = nxt;
        }
        void marge(const Node &lchild, const Node &rchild) {
            nxtsame = min(lchild.nxtsame, rchild.nxtsame);
        }
    };
 
    vector<Node> Tree;
 
    void build(vector<int> &arr, int node, int a, int b) {
        if (a == b) {
            return void(Tree[node].assignLeaf(arr[a]));
        }
        int lchild = node * 2;
        int rchild = node * 2 + 1;
        int mid = (a + b) / 2;
        build(arr, lchild, a, mid);
        build(arr, rchild, mid + 1, b);
        Tree[node].marge(Tree[lchild], Tree[rchild]);
    }
 
    void push(int node, int a, int b) {
        if (Tree[node].lazy == 0) {
            return;
        }
        if (a != b) {
            int lchild = node * 2;
            int rchild = node * 2 + 1;
            Tree[lchild].lazy += Tree[node].lazy; Tree[lchild].lazy %= chars;
            Tree[rchild].lazy += Tree[node].lazy; Tree[rchild].lazy %= chars;
        }
        if (a == b) {
            Tree[node].value += Tree[node].lazy;
            Tree[node].value %= chars;
        }
        Tree[node].lazy = 0;
    }
 
    void update(int node, int a, int b, int i, int j, int val) {
        push(node, a, b);
        if (a > b or a > j or b < i) {
            return;
        }
        if (a >= i and b <= j) {
            Tree[node].lazy += val;
            push(node, a, b);
            return;
        }
        int lchild = node * 2;
        int rchild = node * 2 + 1;
        int mid = (a + b) / 2;
        update(lchild, a, mid, i, j, val);
        update(rchild, mid + 1, b, i, j, val);
        Tree[node].marge(Tree[lchild], Tree[rchild]);
    }
 
    void update(int node, int a, int b, int pos, int nxtsame) {
        push(node, a, b);
        if (a > b or a > pos or b < pos) {
            return;
        }
        if (a >= pos and b <= pos) {
            Tree[node].assignLeafNxtsame(nxtsame);
            return;
        }
        int lchild = node * 2;
        int rchild = node * 2 + 1;
        int mid = (a + b) / 2;
        update(lchild, a, mid, pos, nxtsame);
        update(rchild, mid + 1, b, pos, nxtsame);
        Tree[node].marge(Tree[lchild], Tree[rchild]);
    }
 
    Node query(int node, int a, int b, int pos) {
        push(node, a, b);
        if (a > b or a > pos or b < pos) {
            return Node(-1, INF, 0);
        }
        if (a >= pos and b <= pos) {
            return Tree[node];
        }
        int lchild = node * 2;
        int rchild = node * 2 + 1;
        int mid = (a + b) / 2;
        if (pos <= mid) {
            return query(lchild, a, mid, pos);
        }
        return query(rchild, mid + 1, b, pos);
    }
 
    Node query(int node, int a, int b, int i, int j) {
        push(node, a, b);
        if (a > b or a > j or b < i) {
            return Node();
        }
        if (a >= i and b <= j) {
            return Tree[node];
        }
        int lchild = node * 2;
        int rchild = node * 2 + 1;
        int mid = (a + b) / 2;
        Node p = query(lchild, a, mid, i, j);
        Node q = query(rchild, mid + 1, b, i, j);
        Node res;
        res.marge(p, q);
        return res;
    }
 
    void solve() {
        int n, q;
        cin >> n >> q;
        string s;
        cin >> s;
        vector<int> arr(n + 1);
        for (int i = 1; i <= n; i++) {
            arr[i] = s[i - 1] - 'a';
        }
        Tree.clear(); Tree.resize(4 * n);
        build(arr, 1, 1, n);
        function<void(int)> PointUpdate = [&](int i) {
            if (i < 1) {
                return;
            }
            int val1 = query(1, 1, n, i).value;
            int val2 = query(1, 1, n, i + 1).value;
            int val3 = query(1, 1, n, i + 2).value;
            if (val1 == val2) {
                update(1, 1, n, i, i + 1);
            } else if (val1 == val3) {
                update(1, 1, n, i, i + 2);
            } else {
                update(1, 1, n, i, INF);
            }
        };
        for (int i = 1; i <= n; i++) {
            PointUpdate(i);
        }
        while (q--) {
            int type;
            cin >> type;
            if (type == 1) {
                int l, r, x;
                cin >> l >> r >> x;
                x %= chars;
                update(1, 1, n, l, r, x);
                PointUpdate(r);
                PointUpdate(r - 1);
                PointUpdate(r - 2);
                PointUpdate(l - 1);
                PointUpdate(l - 2);
            } else {
                int l, r;
                cin >> l >> r;
                Node res = query(1, 1, n, l, r);
                cout << (res.nxtsame > r ? "YES" : "NO") << endl;
            }
        }
    }
 
    signed main() {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr); cout.tie(nullptr);
        cout.precision(12);
 
        bool FILEIO = true; string FILE = "in.txt";
        if (FILEIO and fopen(FILE.c_str(), "r")) {
            freopen(FILE.c_str(), "r", stdin);
        }
 
        int tc;
        cin >> tc;
        for (int tcase = 1; tcase <= tc; tcase++) {
            solve();
        } 

}