結果

問題 No.879 Range Mod 2 Query
コンテスト
ユーザー ooaiu
提出日時 2024-11-19 15:41:50
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 285 ms / 3,000 ms
コード長 1,928 bytes
コンパイル時間 3,532 ms
コンパイル使用メモリ 257,416 KB
実行使用メモリ 14,804 KB
最終ジャッジ日時 2024-11-19 15:41:59
合計ジャッジ時間 8,793 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) (void(0))
#endif

#include <atcoder/lazysegtree>
struct S {
    long long sum;
    long long odd, even;
};
S op(S a, S b) {
    return S{
        a.sum + b.sum,
        a.odd + b.odd,
        a.even + b.even,
    };
}
S e() {
    return S{0, 0, 0};
}

struct F {
    long long psum;
    int type;  // 0 -> add
    long long nsum;
};

F id() { return F{0, 0, 0}; }
S mapping(F f, S x) {
    if (f.type == 1) {
        if (f.psum & 1) swap(x.odd, x.even);
        S res = S{
            x.odd + f.nsum * (x.odd + x.even),
            x.odd,
            x.even};
        if (f.nsum & 1) swap(res.odd, res.even);
        return res;
    } else {
        S res = x;
        res.sum += f.nsum * (x.odd + x.even);
        if (f.nsum & 1) swap(res.odd, res.even);
        return res;
    }
}

F composition(F f, F g) {
    if (f.type == 1) {
        F res;
        res.psum = g.psum + g.nsum + f.psum;
        res.type = 1;
        res.nsum = f.nsum;
        return res;
    }
    g.nsum += f.nsum;
    return g;
}
void solve() {
    int N, Q;
    cin >> N >> Q;
    vector<S> init(N);
    for (int i = 0; i < N; i++) {
        int a;
        cin >> a;
        init[i] = S{a, a & 1, ~a & 1};
    }
    atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg(init);
    while (Q--) {
        int o;
        cin >> o;
        if (o == 1) {
            int l, r;
            cin >> l >> r;
            seg.apply(l - 1, r, F{0, 1, 0});
        } else if (o == 2) {
            int l, r, x;
            cin >> l >> r >> x;
            seg.apply(l - 1, r, F{0, 0, x});
        } else {
            int l, r;
            cin >> l >> r;
            S ans = seg.prod(l - 1, r);
            cout << ans.sum << endl;
        }
    }
}

int main() {
    int T = 1;
    // std::cin >> T;
    while (T--) {
        solve();
    }
}
0