#1162066 (C++23) No.879 Range Mod 2 Query

• 問題: No.879 Range Mod 2 Query
• ユーザー: WutongDeath
• 提出日時: 2026-05-01 17:45:30
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 107 ms / 3,000 ms
• コード長: 4,025 bytes
• コンパイル時間: 1,799 ms
• コンパイル使用メモリ: 153,852 KB
• 実行使用メモリ: 16,640 KB
• 最終ジャッジ日時: 2026-05-01 17:45:35
• 合計ジャッジ時間: 3,585 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

ファイルパターン	結果
sample	AC * 1
other	AC * 21

ソースコード

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 100010;

typedef long long LL;

int n, q, a[N];

struct Node {
    int l, r;
    int odd_cnt, even_cnt;
    LL sum, pre_add, add;
    bool lz;
};
struct SegTree {
    Node seg[N << 2];
    void PushUp(int u) {
        seg[u].odd_cnt = seg[u << 1].odd_cnt + seg[u << 1 | 1].odd_cnt;
        seg[u].even_cnt = seg[u << 1].even_cnt + seg[u << 1 | 1].even_cnt;
        seg[u].sum = seg[u << 1].sum + seg[u << 1 | 1].sum;
    }
    void PushDown(int u) {
        LL pa = seg[u].pre_add, a = seg[u].add;
        bool lz = seg[u].lz;
        if (!lz && !a) return;
        if (lz) {
            for (int c : { u << 1, u << 1 | 1 }) {
                int c_len = seg[c].r - seg[c].l + 1;
                // combined pre_add for c = c.pre_add + c.add + pa
                seg[c].pre_add += seg[c].add + pa;
                if (pa % 2) swap(seg[c].odd_cnt, seg[c].even_cnt);
                seg[c].lz = true;
                seg[c].sum = seg[c].odd_cnt;
                seg[c].add = a;
                seg[c].sum += a * c_len;
                if (a % 2) swap(seg[c].odd_cnt, seg[c].even_cnt);
            }
            seg[u].pre_add = 0;
            seg[u].lz = false;
            seg[u].add = 0;
        } else {
            seg[u << 1].add += seg[u].add;
            seg[u << 1].sum += seg[u].add * (seg[u << 1].r - seg[u << 1].l + 1);
            if (seg[u].add % 2) swap(seg[u << 1].odd_cnt, seg[u << 1].even_cnt);
            seg[u << 1 | 1].add += seg[u].add;
            seg[u << 1 | 1].sum += seg[u].add * (seg[u << 1 | 1].r - seg[u << 1 | 1].l + 1);
            if (seg[u].add % 2) swap(seg[u << 1 | 1].odd_cnt, seg[u << 1 | 1].even_cnt);
            seg[u].add = 0LL;
            seg[u].add = 0;
        }
    }
    void Build(int u, int l, int r) {
        seg[u] = { l, r, 0, 0, 0LL, 0LL, 0LL, false };
        if (l == r) {
            if (a[l] % 2) ++seg[u].odd_cnt;
            else ++seg[u].even_cnt;
            seg[u].sum += a[l];
            return;
        }
        int mid = l + r >> 1;
        Build(u << 1, l, mid);
        Build(u << 1 | 1, mid + 1, r);
        PushUp(u);
    }
    void Unify(int u, int l, int r) {
        if (l <= seg[u].l && seg[u].r <= r) {
            seg[u].pre_add += seg[u].add;
            seg[u].lz = true;
            seg[u].sum = seg[u].odd_cnt;
            seg[u].add = 0LL;
            return;
        }
        PushDown(u);
        int mid = seg[u].l + seg[u].r >> 1;
        if (mid >= l) Unify(u << 1, l, r);
        if (mid + 1 <= r) Unify(u << 1 | 1, l, r);
        PushUp(u);
    }
    void Add(int u, int l, int r, int x) {
        if (l <= seg[u].l && seg[u].r <= r) {
            seg[u].add += x;
            seg[u].sum += 1LL * x * (seg[u].r - seg[u].l + 1);
            if (x % 2) swap(seg[u].odd_cnt, seg[u].even_cnt);
            return;
        }
        PushDown(u);
        int mid = seg[u].l + seg[u].r >> 1;
        if (mid >= l) Add(u << 1, l, r, x);
        if (mid + 1 <= r) Add(u << 1 | 1, l, r, x);
        PushUp(u);
    }
    LL QuerySum(int u, int l, int r) {
        if (l <= seg[u].l && seg[u].r <= r) return seg[u].sum;
        PushDown(u);
        LL ret = 0LL;
        int mid = seg[u].l + seg[u].r >> 1;
        if (mid >= l) ret += QuerySum(u << 1, l, r);
        if (mid + 1 <= r) ret += QuerySum(u << 1 | 1, l, r);
        return ret;
    }
} sgt;

int main() {
    // freopen("test.in", "r", stdin);
    // freopen("test.out", "w", stdout);

    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    sgt.Build(1, 1, n);

    for (int i = 1, op, l, r, x; i <= q; ++i) {
        scanf("%d", &op);
        if (op == 1) {
            scanf("%d%d", &l, &r);
            sgt.Unify(1, l, r);
        } else if (op == 2) {
            scanf("%d%d%d", &l, &r, &x);
            sgt.Add(1, l, r, x);
        } else if (op == 3) {
            scanf("%d%d", &l, &r);
            printf("%lld\n", sgt.QuerySum(1, l, r));
        }
    }

    return 0;
}