結果

問題 No.879 Range Mod 2 Query
ユーザー t33ft33f
提出日時 2020-01-14 20:47:49
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 294 ms / 3,000 ms
コード長 4,737 bytes
コンパイル時間 830 ms
コンパイル使用メモリ 67,980 KB
実行使用メモリ 10,864 KB
最終ジャッジ日時 2023-08-27 02:38:19
合計ジャッジ時間 6,367 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,384 KB
testcase_01 AC 3 ms
4,384 KB
testcase_02 AC 3 ms
4,380 KB
testcase_03 AC 3 ms
4,380 KB
testcase_04 AC 3 ms
4,384 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 2 ms
4,384 KB
testcase_07 AC 3 ms
4,380 KB
testcase_08 AC 4 ms
4,380 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 2 ms
4,380 KB
testcase_11 AC 294 ms
10,540 KB
testcase_12 AC 173 ms
10,628 KB
testcase_13 AC 215 ms
10,240 KB
testcase_14 AC 184 ms
10,660 KB
testcase_15 AC 180 ms
7,036 KB
testcase_16 AC 254 ms
10,508 KB
testcase_17 AC 274 ms
10,864 KB
testcase_18 AC 286 ms
10,592 KB
testcase_19 AC 280 ms
10,552 KB
testcase_20 AC 280 ms
10,616 KB
testcase_21 AC 285 ms
10,556 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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 };
        }
    };
    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) {
        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);
            else force(2*i+1, l, m);
            if (m < b) add(a, b, x, 2*i+2, m, r);
            else force(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);
            else force(2*i+1, l, m);
            if (m < b) mod2(a, b, 2*i+2, m, r);
            else force(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