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

提出ソース

結果

問題	No.879 Range Mod 2 Query
ユーザー	🍮かんプリン
提出日時	2020-10-15 18:42:11
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	308 ms / 3,000 ms
コード長	6,265 bytes
コンパイル時間	2,032 ms
コンパイル使用メモリ	172,088 KB
実行使用メモリ	11,912 KB
最終ジャッジ日時	2023-09-28 01:15:29
合計ジャッジ時間	8,089 ms
ジャッジサーバーID （参考情報）	judge13 / judge11

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,380 KB
testcase_01	AC	3 ms 4,380 KB
testcase_02	AC	3 ms 4,380 KB
testcase_03	AC	3 ms 4,376 KB
testcase_04	AC	3 ms 4,376 KB
testcase_05	AC	3 ms 4,376 KB
testcase_06	AC	2 ms 4,376 KB
testcase_07	AC	3 ms 4,380 KB
testcase_08	AC	3 ms 4,384 KB
testcase_09	AC	2 ms 4,376 KB
testcase_10	AC	3 ms 4,376 KB
testcase_11	AC	276 ms 11,380 KB
testcase_12	AC	166 ms 11,412 KB
testcase_13	AC	214 ms 11,496 KB
testcase_14	AC	193 ms 11,528 KB
testcase_15	AC	197 ms 7,608 KB
testcase_16	AC	272 ms 11,596 KB
testcase_17	AC	296 ms 11,912 KB
testcase_18	AC	308 ms 11,700 KB
testcase_19	AC	269 ms 11,524 KB
testcase_20	AC	261 ms 11,612 KB
testcase_21	AC	289 ms 11,720 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

/**
 *   @FileName	a.cpp
 *   @Author	kanpurin
 *   @Created	2020.10.15 18:42:06
**/

#include "bits/stdc++.h" 
using namespace std; 
typedef long long ll;

template <class S,
          S (*op)(S, S),
          S (*e)(),
          class F,
          S (*mapping)(F, S),
          F (*composition)(F, F),
          F (*id)()>
struct lazy_segtree {
  public:
    lazy_segtree() : lazy_segtree(0) {}
    lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
    lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = 0;
        while ((1U << log) < (unsigned int)(_n)) log++;
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        lz = std::vector<F>(size, id());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }
    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }
    S get(int p) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        return d[p];
    }
    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return e();
        l += size;
        r += size;
        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push(r >> i);
        }
        S sml = e(), smr = e();
        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }
    S all_prod() { return d[1]; }
    void apply(int p, F f) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = mapping(f, d[p]);
        for (int i = 1; i <= log; i++) update(p >> i);
    }
    void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return;
        l += size;
        r += size;
        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }
        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) all_apply(l++, f);
                if (r & 1) all_apply(--r, f);
                l >>= 1;
                r >>= 1;
            }
            l = l2;
            r = r2;
        }
        for (int i = 1; i <= log; i++) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }
    template <bool (*g)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return g(x); });
    }
    template <class G> int max_right(int l, G g) {
        assert(0 <= l && l <= _n);
        assert(g(e()));
        if (l == _n) return _n;
        l += size;
        for (int i = log; i >= 1; i--) push(l >> i);
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!g(op(sm, d[l]))) {
                while (l < size) {
                    push(l);
                    l = (2 * l);
                    if (g(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }
    template <bool (*g)(S)> int min_left(int r) {
        return min_left(r, [](S x) { return g(x); });
    }
    template <class G> int min_left(int r, G g) {
        assert(0 <= r && r <= _n);
        assert(g(e()));
        if (r == 0) return 0;
        r += size;
        for (int i = log; i >= 1; i--) push((r - 1) >> i);
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!g(op(d[r], sm))) {
                while (r < size) {
                    push(r);
                    r = (2 * r + 1);
                    if (g(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }
  private:
    int _n, size, log;
    std::vector<S> d;
    std::vector<F> lz;
    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
    void all_apply(int k, F f) {
        d[k] = mapping(f, d[k]);
        if (k < size) lz[k] = composition(f, lz[k]);
    }
    void push(int k) {
        all_apply(2 * k, lz[k]);
        all_apply(2 * k + 1, lz[k]);
        lz[k] = id();
    }
};

struct S {
    ll val;
    int size;
    int odd;
};

struct F {
    ll a,b,c; 
};

S op(S l, S r) { return S{l.val + r.val, l.size + r.size, l.odd + r.odd}; }

S e() { return S{0,0,0}; }


S mapping(F f, S s) {
    if (f.a == 0) return S{s.val + f.c * s.size, s.size, f.c % 2 == 0 ? s.odd : s.size - s.odd};
    if (f.b == 0) {
        return S{s.odd+f.c*s.size,s.size,f.c % 2 == 0 ? s.odd : s.size - s.odd};
    }
    return S{s.size-s.odd+f.c*s.size,s.size,f.c % 2 == 0 ? s.size-s.odd : s.odd};
}

F composition(F f, F g) {
    if (f.a == 0 && g.a == 0) return F{0,0,f.c+g.c};
    if (f.a == 0 && g.a != 0) return F{1,g.b,f.c+g.c};
    if (f.a != 0 && g.a == 0) return F{1,(f.b+g.c)%2,f.c};
    return F{1,(f.b+g.b+g.c) % 2,f.c};
}


F id() { return F{0,0,0}; }

int main() {
    int n,q;cin >> n >> q;
    vector<S> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i].val;
        a[i].odd = (a[i].val % 2 == 0 ? 0 : 1);
        a[i].size = 1;
    }
    lazy_segtree<S,op,e,F,mapping,composition,id> seg(a);
    while(q--) {
        int t;cin >> t;
        if (t == 1) {
            int l,r;cin >> l >> r;
            seg.apply(l-1,r,F{1,0,0});
        }
        else if (t == 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;
            cout << seg.prod(l-1,r).val << endl;
        }
    }
    return 0;
}

yukicoder

結果

テストケース

ソースコード