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

• 問題: No.879 Range Mod 2 Query
• ユーザー: WutongDeath
• 提出日時: 2026-05-01 17:15:01
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 3,418 bytes
• コンパイル時間: 1,806 ms
• コンパイル使用メモリ: 153,988 KB
• 実行使用メモリ: 14,592 KB
• 最終ジャッジ日時: 2026-05-01 17:15:08
• 合計ジャッジ時間: 4,703 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_1

ファイルパターン	結果
sample	AC * 1
other	AC * 3 WA * 18

ソースコード

#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, 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) {
        if (seg[u].lz) {
            seg[u << 1].lz = seg[u << 1 | 1].lz = true;
            seg[u << 1].sum = seg[u << 1].odd_cnt;
            seg[u << 1 | 1].sum = seg[u << 1 | 1].odd_cnt;
            seg[u << 1].add = seg[u << 1 | 1].add = 0;
            seg[u].lz = false;
        }
        if (seg[u].add) {
            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;
        }
    }
    void Build(int u, int l, int r) {
        seg[u] = { l, r, 0, 0, 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].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() {
    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;
}