#417488 (C++14) No.879 Range Mod 2 Query

• 問題: No.879 Range Mod 2 Query
• ユーザー: t33f
• 提出日時: 2020-01-14 20:47:49
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 299 ms / 3,000 ms
• コード長: 4,737 bytes
• コンパイル時間: 675 ms
• コンパイル使用メモリ: 70,496 KB
• 実行使用メモリ: 10,904 KB
• 最終ジャッジ日時: 2024-06-07 22:28:09
• 合計ジャッジ時間: 4,736 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,816 KB
testcase_01	AC	3 ms; 6,940 KB
testcase_02	AC	3 ms; 6,944 KB
testcase_03	AC	3 ms; 6,944 KB
testcase_04	AC	3 ms; 6,944 KB
testcase_05	AC	3 ms; 6,944 KB
testcase_06	AC	2 ms; 6,944 KB
testcase_07	AC	3 ms; 6,944 KB
testcase_08	AC	3 ms; 6,944 KB
testcase_09	AC	3 ms; 6,940 KB
testcase_10	AC	3 ms; 6,940 KB
testcase_11	AC	287 ms; 10,656 KB
testcase_12	AC	168 ms; 10,672 KB
testcase_13	AC	221 ms; 10,684 KB
testcase_14	AC	198 ms; 10,756 KB
testcase_15	AC	198 ms; 7,040 KB
testcase_16	AC	280 ms; 10,708 KB
testcase_17	AC	285 ms; 10,812 KB
testcase_18	AC	293 ms; 10,756 KB
testcase_19	AC	277 ms; 10,904 KB
testcase_20	AC	280 ms; 10,760 KB
testcase_21	AC	299 ms; 10,692 KB

ソースコード

#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;
        }
    }
}