結果

問題 No.879 Range Mod 2 Query
コンテスト
ユーザー pghk
提出日時 2025-10-20 23:34:40
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,530 bytes
コンパイル時間 3,506 ms
コンパイル使用メモリ 287,908 KB
実行使用メモリ 15,400 KB
最終ジャッジ日時 2025-10-20 23:34:48
合計ジャッジ時間 8,147 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 3 WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, j, N) for (int i = j; i < N; i++)

const int MAX_N = 100009;

struct LSG{
    struct node{
        ll sum = 0;
        ll add = 0;
        int cntodd = 0;
        int len = 0;
        bool toparity = false;
    };
    int n;
    vector<node> st;

    LSG(int n_) {
        n = n_;
        st.resize(4*n);
        build(1, 0, n);
    }

    void build(int p, int l, int r) {
        st[p].len = r - l;
        if (r - l == 1) return;
        int m = (l + r) / 2;
        build(p << 1, l, m);
        build(p << 1 | 1, m, r);
    }

    void pull(int p) {
        st[p].sum = st[p<<1].sum + st[p<<1|1].sum;
        st[p].cntodd = st[p<<1].cntodd + st[p<<1|1].cntodd;
    }

    void apply_add(int p ,ll x) {
        if (x == 0) return;
        st[p].sum += x * st[p].len;
        if (x & 1) st[p].cntodd = st[p].len - st[p].cntodd;
        st[p].add += x;
    }

    void apply_toparity(int p) {
        st[p].sum = st[p].cntodd;
        st[p].add = 0;
        st[p].toparity = true;
    }

    void push(int p) {
        if (st[p].toparity) {
            apply_toparity(p << 1);
            apply_toparity(p << 1 | 1);
            st[p].toparity = false;
        }
        if (st[p].add != 0) {
            apply_add(p<<1, st[p].add);
            apply_add(p<<1|1, st[p].add);
            st[p].add = 0;
        }
    }

    void point_init(int idx, ll val) {
        point_init(1, 0, n, idx, val);
    }
    void point_init(int p, int l, int r, int idx, ll val) {
        if (r - l == 1) {
            st[p].sum = val;
            st[p].cntodd = (val & 1) ? 1 : 0;
            return;
        }
        int m = (l + r) / 2;
        if (idx < m) point_init(p << 1, l, m, idx, val);
        else point_init(p<<1|1, m, r, idx, val);
        pull(p);
    }

    void range_add(int l, int r, ll x) {
        range_add(1, 0, n, l, r, x);
    }
    void range_add(int p, int l, int r, int L, int R, ll x) {
        if (r <= L || R <= l) return;
        if (L <= l && r <= R) {
            apply_add(p, x);
            return;
        }
        push(p);
        int m = (l+r)/2;
        range_add(p<<1, l, m, L, R, x);
        range_add(p<<1|1, m, r, L, R, x);
        pull(p);
    }

    void range_toparity(int L, int R) {
        range_toparity(1, 0, n, L, R);
    }
    void range_toparity(int p, int l, int r, int L, int R) {
        if (r <= L || R <= l) return;
        if (L <= l && r <= R) {
            apply_toparity(p);
            return;
        }
        push(p);
        int m = (l + r) / 2;
        range_toparity(p<<1, l, m, L, R);
        range_toparity(p<<1|1, m, r, L, R);
        pull(p);
    }

    ll range_sum(int L, int R) { return range_sum(1, 0, n, L, R); }
    ll range_sum(int p, int l, int r, int L, int R) {
        if (r <= L || R <= l) return 0;
        if (L <= l && r <= R) return st[p].sum;
        push(p);
        int m = (l + r) >> 1;
        return range_sum(p<<1, l, m, L, R) + range_sum(p<<1|1, m, r, L, R);
    }
};

int main() {
    int N, Q;
    cin >> N >> Q;
    LSG lsg(N);
    rep(i, 0, N) {
        ll a; cin >> a;
        lsg.point_init(i, a);
    }

    rep(_, 0, Q) {
        int q, l, r; cin >> q >> l >> r;
        l--; r--;
        if (q == 1) {
            lsg.range_toparity(l, r+1);
        }
        else if (q == 2) {
            ll x; cin >> x;
            lsg.range_add(l, r+1, x);
        }
        else {
            cout << lsg.range_sum(l, r+1) << endl;
        }
    }

    return 0;
}
0