結果

問題 No.1000 Point Add and Array Add
コンテスト
ユーザー risujiroh
提出日時 2020-02-28 21:34:38
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 168 ms / 2,000 ms
コード長 2,724 bytes
コンパイル時間 1,624 ms
コンパイル使用メモリ 176,396 KB
実行使用メモリ 11,064 KB
最終ジャッジ日時 2024-10-13 16:58:52
合計ジャッジ時間 4,478 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

template <class T, class U, class Op, class Apply, class Compose>
struct lazy_segtree {
  const Op op;
  const T e;
  const Apply ap;
  const Compose cp;
  const U id;
  const int n;
  vector<T> t;
  vector<U> u;
  lazy_segtree(int _n, Op _op, T _e, Apply _ap, Compose _cp, U _id) :
    op(_op), e(_e), ap(_ap), cp(_cp), id(_id), n(_n), t(2 * n, e), u(n, id) {}
  T& operator[](int i) { return t[n + i]; }
  void build() { for (int i = n; i-- > 1; ) t[i] = op(t[2 * i], t[2 * i + 1]); }
  void push() { for (int i = 1; i < n; ++i) push(i); }
  void apply(int i, U f) {
    t[i] = ap(t[i], f);
    if (i < n) u[i] = cp(u[i], f);
  }
  void push(int i) {
    apply(2 * i, u[i]), apply(2 * i + 1, u[i]);
    u[i] = id;
  }
  void propagate(int i) {
    for (int h = __lg(i), tz = __builtin_ctz(i); h > tz; --h) push(i >> h);
  }
  T fold(int l, int r) {
    propagate(l += n), propagate(r += n);
    T a = e, b = e;
    for (; l < r; l >>= 1, r >>= 1) {
      if (l & 1) a = op(a, t[l++]);
      if (r & 1) b = op(t[--r], b);
    }
    return op(a, b);
  }
  T get(int i) { return fold(i, i + 1); }
  void act(int l, int r, U f) {
    propagate(l += n), propagate(r += n);
    for (int i = l, j = r; i < j; i >>= 1, j >>= 1) {
      if (i & 1) apply(i++, f);
      if (j & 1) apply(--j, f);
    }
    l = l >> __builtin_ctz(l);
    while (l >>= 1) t[l] = op(t[2 * l], t[2 * l + 1]);
    r = r >> __builtin_ctz(r);
    while (r >>= 1) t[r] = op(t[2 * r], t[2 * r + 1]);
  }
  void set(int i, T a) {
    propagate(i += n), propagate(i + 1);
    t[i] = a;
    while (i >>= 1) t[i] = op(t[2 * i], t[2 * i + 1]);
  }
};
template <class T, class U, class Op, class Apply, class Compose>
auto make_lazy_segtree(int n, Op op, T e, Apply ap, Compose cp, U id) {
  return lazy_segtree<T, U, Op, Apply, Compose>(n, op, e, ap, cp, id);
}

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n, q;
  cin >> n >> q;
  using p = pair<long long, long long>;
  auto st = make_lazy_segtree<p>(n, [](auto l, auto r) -> p {
    return {l.first + r.first, l.second + r.second};
  }, {0, 0}, [](auto a, auto f) -> p {
    return {a.first + a.second * f, a.second};
  }, [](auto f, auto g) {
    return f + g;
  }, 0LL);
  for (int i = 0; i < n; ++i) {
    int a;
    cin >> a;
    st[i] = {0, a};
  }
  st.build();
  while (q--) {
    char c;
    cin >> c;
    if (c == 'A') {
      int i, x;
      cin >> i >> x;
      --i;
      auto e = st.get(i);
      st.set(i, {e.first, e.second + x});
    } else {
      int l, r;
      cin >> l >> r;
      --l;
      st.act(l, r, 1);
    }
  }
  st.push();
  for (int i = 0; i < n; ++i) {
    cout << st[i].first << " \n"[i == n - 1];
  }
}
0