結果

問題 No.879 Range Mod 2 Query
コンテスト
ユーザー t33f
提出日時 2020-01-14 20:22:43
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 4,673 bytes
記録
コンパイル時間 691 ms
コンパイル使用メモリ 69,736 KB
実行使用メモリ 10,968 KB
最終ジャッジ日時 2024-12-26 06:34:39
合計ジャッジ時間 5,486 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other WA * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
using namespace std;

class SegTreeLazy {
    long long *data;
    int *odd_count;
    enum MODOP { NOP, MOD, MODNEG };
    struct op {
        MODOP mop;
        long long incr;
        op() : mop(NOP), incr(0) {};
        op(MODOP mop, long long incr) : mop(mop), incr(incr) {};
        op append(op next) {
            if (next.mop == NOP) return { mop, incr + next.incr };
            const bool neg_flag = (incr % 2) ^ (mop == MODNEG) ^ (next.mop == MODNEG);
            return { (neg_flag ? MODNEG : MOD), next.incr };
        }
    }; // mod and then add
    op *lazy;
    int N;
    string to_str(MODOP mop) {
        if (mop == NOP) return "NOP";
        if (mop == MOD) return "MOD";
        if (mop == MODNEG) return "MODNEG";
        return "";
    }
    void force(int i, int l, int r) {
        const int w = r - l;
        const int m = (r + l) / 2;
        switch (lazy[i].mop) {
        case NOP:
            data[i] += (long long)lazy[i].incr * (r - l);
            if (lazy[i].incr % 2) odd_count[i] = r - l - odd_count[i];
            break;
        case MOD:
            data[i] = odd_count[i] + (long long)lazy[i].incr * (r - l);
            if (lazy[i].incr % 2) odd_count[i] = r - l - odd_count[i];
            break;
        case MODNEG:
            data[i] = r - l - odd_count[i] + (long long)lazy[i].incr * (r - l);
            if (lazy[i].incr % 2 == 0) odd_count[i] = r - l - odd_count[i];
            break;
        }
        if (r - l > 1) {
            lazy[2*i+1] = lazy[2*i+1].append(lazy[i]);
            lazy[2*i+2] = lazy[2*i+2].append(lazy[i]);
        }
        lazy[i] = { NOP, 0 };
    }
    void recalc(int i) {
        data[i] = data[2*i+1] + data[2*i+2];
        odd_count[i] = odd_count[2*i+1] + odd_count[2*i+2];
    }
public:
    SegTreeLazy(int size, int *a) {
        N = 1;
        while (N < size) N *= 2;
        data = new long long[2*N]();
        odd_count = new int[2*N]();
        lazy = new op[2*N]();
        for (int i = 0; i < size; i++) {
            data[i+N-1] = a[i];
            odd_count[i+N-1] = a[i]%2;
        }
        for (int i = N-2; i >= 0; i--) {
            recalc(i);
        }
    }
    ~SegTreeLazy() {
        delete[] data;
        delete[] lazy;
        delete[] odd_count;
    }
    long long sum(int a, int b, int i=0, int l=0, int r=0) {
        if (i == 0) r = N;
        if (b <= l || r <= a) return 0;
        force(i, l, r);
        if (a <= l && r <= b) return data[i];
        const int m = (l+r)/2;
        if (b <= m) return sum(a, b, 2*i+1, l, m);
        if (m <= a) return sum(a, b, 2*i+2, m, r);
        return sum(a, b, 2*i+1, l, m) + sum(a, b, 2*i+2, m, r);
    }
    void add(int a, int b, int x, int i=0, int l=0, int r=0) {
        if (i == 0) r = N;
        if (b <= l || r <= a) return;
        if (a <= l && r <= b) {
            lazy[i].incr += x;
            force(i, l, r);
        } else {
            force(i, l, r);
            const int m = (l+r)/2;
            if (a < m) add(a, b, x, 2*i+1, l, m);
            if (m < b) add(a, b, x, 2*i+2, m, r);
            recalc(i);
        }
    }
    void mod2(int a, int b, int i=0, int l=0, int r=0) {
        if (i == 0) r = N;
        if (b <= l || r <= a) return;
        if (a <= l && r <= b) {
            lazy[i] = lazy[i].append({ MOD, 0 });
            force(i, l, r);
        } else {
            force(i, l, r);
            const int m = (l+r)/2;
            if (a < m) mod2(a, b, 2*i+1, l, m);
            if (m < b) mod2(a, b, 2*i+2, m, r);
            recalc(i);
        }
    }
    void dump() {
        cerr << "---\n";
        for (int i = 1; i <= N; i *= 2) {
            for (int j = i-1; j < 2*i-1; j++)
                cerr << data[j] << ' ';
            cerr << endl;
        }
        for (int i = 1; i <= N; i *= 2) {
            for (int j = i-1; j < 2*i-1; j++)
                cerr << odd_count[j] << ' ';
            cerr << endl;
        }
        for (int i = 1; i <= N; i *= 2) {
            for (int j = i-1; j < 2*i-1; j++)
                cerr << '[' << lazy[j].mop << ' ' << lazy[j].incr << "] ";
            cerr << endl;
        }
        cerr << "---\n";
    }
};

int main() {
    int n, q; cin >> n >> q;
    int a[n]; for (int i = 0; i < n; i++) cin >> a[i];
    SegTreeLazy st(n, a);

    while (q--) {
        int k; cin >> k;
        if (k == 1) {
            int l, r; cin >> l >> r;
            st.mod2(l-1, r);
        }
        if (k == 2) {
            int l, r, x; cin >> l >> r >> x;
            st.add(l-1, r, x);
        }
        if (k == 3) {
            int l, r; cin >> l >> r;
            cout << st.sum(l-1, r) << endl;
        }
    }
}
0