結果

問題 No.879 Range Mod 2 Query
コンテスト
ユーザー hos.lyric
提出日時 2019-09-20 00:58:35
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 279 ms / 3,000 ms
コード長 4,084 bytes
記録
コンパイル時間 1,949 ms
コンパイル使用メモリ 127,888 KB
実行使用メモリ 14,316 KB
最終ジャッジ日時 2024-07-22 07:43:42
合計ジャッジ時間 6,478 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
// #pragma GCC target ("avx")

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> void chmin(T &t, const T &f) { if (t > f) t = f; }
template <class T> void chmax(T &t, const T &f) { if (t < f) t = f; }

template <class T, class S> struct SegmentTree {
  using OpTT = function<T(const T &, const T &)>;
  using OpSS = function<S(const S &, const S &)>;
  using OpST = function<T(const S &, const T &, int)>;
  const OpTT opTT;
  const OpSS opSS;
  const OpST opST;
  const T idT;
  const S idS;

  int n;
  vector<T> ts;
  vector<S> ss;
  SegmentTree(int n_, const OpTT opTT, const OpSS opSS, const OpST opST, const T &idT, const S &idS)
      : opTT(opTT), opSS(opSS), opST(opST), idT(idT), idS(idS) {
    for (n = 1; n < n_; n <<= 1) {}
    ts.assign(n << 1, idT);
    ss.assign(n << 1, idS);
  }
  T &at(int a) {
    return ts[n + a];
  }
  void build() {
    for (int a = n; --a; ) ts[a] = opTT(ts[a << 1], ts[a << 1 | 1]);
  }
  T query(int a, int b, const S &s) {
    return query(1, 0, n, a, b, s);
  }

 private:
  T query(int u, int l, int r, int a, int b, const S &s) {
    chmax(a, l);
    chmin(b, r);
    if (a >= b) return idT;
    if (a == l && b == r) {
      ts[u] = opST(s, ts[u], r - l);
      ss[u] = opSS(s, ss[u]);
      return ts[u];
    }
    const int uL = u << 1, uR = u << 1 | 1;
    const int mid = (l + r) >> 1;
    {
      ts[uL] = opST(ss[u], ts[uL], mid - l);
      ts[uR] = opST(ss[u], ts[uR], r - mid);
      ss[uL] = opSS(ss[u], ss[uL]);
      ss[uR] = opSS(ss[u], ss[uR]);
      ss[u] = idS;
    }
    const T resL = query(uL, l, mid, a, b, s);
    const T resR = query(uR, mid, r, a, b, s);
    ts[u] = opTT(ts[uL], ts[uR]);
    return opTT(resL, resR);
  }
};

struct T {
  Int sum, cnt1;
  T operator*(const T &t) const {
    return T{sum + t.sum, cnt1 + t.cnt1};
  }
};

/*
  t -> t + y
  t -> (t + x) % 2 + y  (x \in {0, 1})
*/
struct S {
  Int x, y;
  S operator*(const S &s) const {
    if (x == -1) {
      return S{s.x, s.y + y};
    } else {
      if (s.x == -1) {
        return S{(s.y + x) & 1, y};
      } else {
        return S{(s.x + s.y + x) & 1, y};
      }
    }
  }
};
T appl(const S &s, const T &t, int sz) {
  T tt = t;
  if (s.x != -1) {
    if (s.x) {
      tt.cnt1 = sz - tt.cnt1;
    }
    tt.sum = tt.cnt1;
  }
  if (s.y & 1) {
    tt.cnt1 = sz - tt.cnt1;
  }
  tt.sum += s.y * sz;
  return tt;
}


constexpr int MAX = 100010;

int N, Q;
Int A[MAX];
int TYP[MAX], L[MAX], R[MAX];
Int X[MAX];

int main() {
  for (; ~scanf("%d%d", &N, &Q); ) {
    for (int i = 0; i < N; ++i) {
      scanf("%lld", &A[i]);
    }
    for (int q = 0; q < Q; ++q) {
      scanf("%d%d%d", &TYP[q], &L[q], &R[q]);
      --L[q];
      if (TYP[q] == 2) {
        scanf("%lld", &X[q]);
      }
    }
    
    SegmentTree<T, S> seg(N, multiplies<T>(), multiplies<S>(), appl, T{0, 0}, S{-1, 0});
    for (int i = 0; i < N; ++i) {
      seg.at(i) = T{A[i], A[i] & 1};
    }
    seg.build();
    for (int q = 0; q < Q; ++q) {
      switch (TYP[q]) {
        case 1: {
          seg.query(L[q], R[q], S{0, 0});
        } break;
        case 2: {
          seg.query(L[q], R[q], S{-1, X[q]});
        } break;
        case 3: {
          const T res = seg.query(L[q], R[q], S{-1, 0});
          printf("%lld\n", res.sum);
        } break;
        default: assert(false);
      }
    }
  }
  return 0;
}
0