結果

問題 No.879 Range Mod 2 Query
ユーザー m_tsubasam_tsubasa
提出日時 2020-07-31 20:04:48
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 333 ms / 3,000 ms
コード長 3,646 bytes
コンパイル時間 2,367 ms
コンパイル使用メモリ 213,432 KB
実行使用メモリ 15,804 KB
最終ジャッジ日時 2023-09-20 20:22:06
合計ジャッジ時間 7,556 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 3 ms
4,376 KB
testcase_02 AC 3 ms
4,376 KB
testcase_03 AC 3 ms
4,380 KB
testcase_04 AC 4 ms
4,376 KB
testcase_05 AC 3 ms
4,380 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 3 ms
4,376 KB
testcase_08 AC 3 ms
4,380 KB
testcase_09 AC 3 ms
4,380 KB
testcase_10 AC 3 ms
4,380 KB
testcase_11 AC 321 ms
14,928 KB
testcase_12 AC 196 ms
14,932 KB
testcase_13 AC 243 ms
14,928 KB
testcase_14 AC 222 ms
15,584 KB
testcase_15 AC 222 ms
9,848 KB
testcase_16 AC 320 ms
15,452 KB
testcase_17 AC 321 ms
15,524 KB
testcase_18 AC 333 ms
15,392 KB
testcase_19 AC 310 ms
15,468 KB
testcase_20 AC 308 ms
15,804 KB
testcase_21 AC 330 ms
15,468 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

// 0-indexed
template <class T, class E>
struct SegmentTreeLaze {
  // a,b:T c,d:E e:E(unit)
  // g(f(a,b),c) = f(g(a,c),g(b,c))
  // g(g(a,c),d) = g(a,h(c,d))
  // g(a,e) = a
  typedef function<T(T, T)> F;
  typedef function<T(T, E)> G;
  typedef function<E(E, E)> H;
  int n, height;
  F f;
  G g;
  H h;
  T tunit;
  E eunit;
  vector<T> dat;
  vector<E> laz;
  SegmentTreeLaze(){};
  SegmentTreeLaze(int newn, F f, G g, H h, T nt, E ne)
      : f(f), g(g), h(h), tunit(nt), eunit(ne) {
    init(newn);
  }
  SegmentTreeLaze(const vector<T> &v, F f, G g, H h, T nt, E ne)
      : f(f), g(g), h(h), tunit(nt), eunit(ne) {
    int _n = v.size();
    init(v.size());
    for (int i = 0; i < _n; ++i) dat[n + i] = v[i];
    for (int i = n - 1; i; --i) dat[i] = f(dat[i << 1], dat[(i << 1) | 1]);
  }
  void init(int newn) {
    n = 1, height = 0;
    while (n < newn) n <<= 1, ++height;
    dat.assign(n << 1, tunit);
    laz.assign(n << 1, eunit);
  }

  inline T reflect(int k) {
    return laz[k] == eunit ? dat[k] : g(dat[k], laz[k]);
  }

  inline void eval(int k) {
    if (laz[k] == eunit) return;
    laz[k << 1] = h(laz[k << 1], laz[k]);
    laz[(k << 1) | 1] = h(laz[(k << 1) | 1], laz[k]);
    dat[k] = reflect(k);
    laz[k] = eunit;
  }

  inline void thrust(int k) {
    for (int i = height; i; --i) eval(k >> i);
    // reset query
    dat[k] = reflect(k);
    laz[k] = eunit;
  }

  void recalc(int k) {
    while (k >>= 1) dat[k] = f(reflect(k << 1), reflect((k << 1) | 1));
  }
  // [a,b)
  void update(int a, int b, E newdata) {
    thrust(a += n);
    thrust(b += n - 1);
    for (int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
      if (l & 1) laz[l] = h(laz[l], newdata), l++;
      if (r & 1) --r, laz[r] = h(laz[r], newdata);
    }
    recalc(a);
    recalc(b);
  }

  void set_val(int k, T newdata) {
    thrust(k += n);
    dat[k] = newdata;
    laz[k] = eunit;
    recalc(k);
  }

  // [a,b)
  T query(int a, int b) {
    thrust(a += n);
    thrust(b += n - 1);
    T vl = tunit, vr = tunit;
    for (int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
      if (l & 1) vl = f(vl, reflect(l++));
      if (r & 1) vr = f(reflect(--r), vr);
    }
    return f(vl, vr);
  }
};

struct dat {
  long long wid, sum, odd;
  dat(long long _w = 1, long long _s = 0, long long _o = 0)
      : wid(_w), sum(_s), odd(_o) {}
};
struct opt {
  int mod;
  long long x;
  opt(int _m = 0, long long _x = 0) : mod(_m), x(_x) {}
  bool operator==(const opt &r) const { return mod == r.mod && x == r.x; }
};

int n, q;
vector<dat> v;
SegmentTreeLaze<dat, opt> seg;

int main() {
  cin >> n >> q;
  v.resize(n);
  for (int i = 0; i < n; ++i) {
    cin >> v[i].sum;
    v[i].odd = v[i].sum & 1;
  }
  {  // make seg
    auto f = [](dat l, dat r) {
      return dat(l.wid + r.wid, l.sum + r.sum, l.odd + r.odd);
    };
    auto g = [](dat l, opt r) {
      if (r.mod == 2) l.odd = l.wid - l.odd;
      if (r.mod) l.sum = l.odd;
      l.sum += l.wid * r.x;
      if (r.x & 1) l.odd = l.wid - l.odd;
      return l;
    };
    auto h = [](opt l, opt r) {
      if (r.mod) {
        l.mod = 1 + ((l.mod / 2) ^ (r.mod / 2) ^ (l.x & 1));
        l.x = 0;
      }
      l.x += r.x;
      return l;
    };
    seg = SegmentTreeLaze<dat, opt>(v, f, g, h, dat(0), opt());
  }
  {  // query
    for (int i = 0; i < q; ++i) {
      long long a, b, c, x;
      cin >> a >> b >> c;
      if (a == 1)
        seg.update(b - 1, c, opt(1, 0));
      else if (a == 2) {
        cin >> x;
        seg.update(b - 1, c, opt(0, x));
      } else
        cout << seg.query(b - 1, c).sum << endl;
    }
  }
  return 0;
}
0