JLCPC2025H.cpp

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 2e5+10;
const int P = 1e9+9;

#define ls (u<<1)
#define rs (u<<1|1)
#define Mid ((L+R) >> 1)

struct SGT {
    int s1[N<<2], s2[N<<2], s3[N<<2], tag[N<<2];
    int a[N];

    void spread(int u, int t, int L, int R) {
        int S1 = s1[u], S2 = s2[u], S3 = s3[u];
        s1[u] = (S1 + (R-L+1) * t) % P;
        s2[u] = (S2 + t*t % P * (R-L+1) % P + 2*t*S1 % P) % P;
        s3[u] = (S3 + t*t % P * t % P * (R-L+1) % P + 3*t*S2 % P + 3*t*t % P * S1 % P) % P;
        tag[u] = (tag[u] + t) % P;
    }

    void pushdown(int u, int L, int R) {
        if (tag[u] == 0) return;
        spread(ls, tag[u], L, Mid);
        spread(rs, tag[u], Mid+1, R);
        tag[u] = 0;
    }

    void pushup(int u) {
        s1[u] = (s1[ls] + s1[rs]) % P;
        s2[u] = (s2[ls] + s2[rs]) % P;
        s3[u] = (s3[ls] + s3[rs]) % P;
    }

    void modify(int u, int l, int r, int t, int L, int R) {
        if (l > r) return;
        if (l <= L && R <= r) return spread(u, t, L, R);
        pushdown(u, L, R);
        if (l <= Mid) modify(ls, l, r, t, L, Mid);
        if (Mid+1 <= r) modify(rs, l, r, t, Mid+1, R);
        pushup(u);
    }

    int query1(int u, int l, int r, int L, int R) {
        if (l > r) return 0;
        if (l <= L && R <= r) return s1[u];
        pushdown(u, L, R);
        int res = 0;
        if (l <= Mid) res = query1(ls, l, r, L, Mid);
        if (Mid+1 <= r) res = (res + query1(rs, l, r, Mid+1, R)) % P;
        return res;
    }

    int query2(int u, int l, int r, int L, int R) {
        if (l > r) return 0;
        if (l <= L && R <= r) return s2[u];
        pushdown(u, L, R);
        int res = 0;
        if (l <= Mid) res = query2(ls, l, r, L, Mid);
        if (Mid+1 <= r) res = (res + query2(rs, l, r, Mid+1, R)) % P;
        return res;
    }

    int query3(int u, int l, int r, int L, int R) {
        if (l > r) return 0;
        if (l <= L && R <= r) return s3[u];
        pushdown(u, L, R);
        int res = 0;
        if (l <= Mid) res = query3(ls, l, r, L, Mid);
        if (Mid+1 <= r) res = (res + query3(rs, l, r, Mid+1, R)) % P;
        return res;
    }

    void build(int u, int L, int R) {
        if (L == R) return s1[u] = a[L], s2[u] = a[L] * a[L], s3[u] = a[L] * a[L] % P * a[L] % P, void();
        build(ls, L, Mid);
        build(rs, Mid+1, R);
        pushup(u);
    }
} t[2];

int n, q;
signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> q;
    for (int i = 1, a; i <= n; i++) {
        cin >> a;
        t[i % 2].a[(i + 1) / 2] = a;
    }
    if (n % 2) n++;
    t[0].build(1, 1, n/2);
    t[1].build(1, 1, n/2);

    for (int i = 1; i <= q; i++) {
        int op, l, r, v;
        cin >> op >> l >> r;

        if (op == 0) {
            cin >> v;
            if (l % 2 && r % 2) {
                t[0].modify(1, (l+1)/2, (r-1)/2, v, 1, n/2);
                t[1].modify(1, (l+1)/2, (r+1)/2, v, 1, n/2);
            }
            else if (!(l % 2) && r % 2) {
                t[0].modify(1, l/2, (r-1)/2, v, 1, n/2);
                t[1].modify(1, (l+2) / 2, (r+1)/2, v, 1, n/2);
            }
            else if (l % 2 && !(r % 2)) {
                t[0].modify(1, (l+1)/2, r/2, v, 1, n/2);
                t[1].modify(1, (l+1)/2, r/2, v, 1, n/2);
            }
            else {
                t[0].modify(1, l/2, r/2, v, 1, n/2);
                t[1].modify(1, (l+2)/2, r/2, v, 1, n/2);
            }
        }
        else {
            if (l % 2) {
                // l 奇， r 偶
                if (
                    t[0].query2(1, (l+1)/2, r/2, 1, n/2) ==
                    t[1].query2(1, (l+1)/2, r/2, 1, n/2) &&
                    t[0].query3(1, (l+1)/2, r/2, 1, n/2) ==
                    t[1].query3(1, (l+1)/2, r/2, 1, n/2)
                ) {
                    cout << "YES\n";
                }
                else cout << "NO\n";
            }
            else {
                if (
                    t[0].query2(1, l/2, (r-1)/2, 1, n/2) ==
                    t[1].query2(1, (l+2)/2, (r+1)/2, 1, n/2) &&
                    t[0].query3(1, l/2, (r-1)/2, 1, n/2) ==
                    t[1].query3(1, (l+2)/2, (r+1)/2, 1, n/2)
                ) {
                    cout << "YES\n";
                }
                else {
                    cout << "NO\n";
                }
            }
        }
    }
    return 0;
}