結果

問題 No.1099 Range Square Sum
ユーザー HaarHaar
提出日時 2020-06-27 20:23:11
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 423 ms / 2,000 ms
コード長 3,701 bytes
コンパイル時間 2,214 ms
コンパイル使用メモリ 207,452 KB
実行使用メモリ 17,120 KB
最終ジャッジ日時 2023-09-19 09:14:38
合計ジャッジ時間 8,711 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 1 ms
4,376 KB
testcase_08 AC 2 ms
4,376 KB
testcase_09 AC 1 ms
4,376 KB
testcase_10 AC 1 ms
4,380 KB
testcase_11 AC 3 ms
4,380 KB
testcase_12 AC 3 ms
4,376 KB
testcase_13 AC 4 ms
4,380 KB
testcase_14 AC 3 ms
4,376 KB
testcase_15 AC 4 ms
4,380 KB
testcase_16 AC 4 ms
4,376 KB
testcase_17 AC 4 ms
4,376 KB
testcase_18 AC 4 ms
4,380 KB
testcase_19 AC 4 ms
4,380 KB
testcase_20 AC 4 ms
4,380 KB
testcase_21 AC 423 ms
16,676 KB
testcase_22 AC 422 ms
17,072 KB
testcase_23 AC 419 ms
17,120 KB
testcase_24 AC 417 ms
17,060 KB
testcase_25 AC 423 ms
16,792 KB
testcase_26 AC 356 ms
17,048 KB
testcase_27 AC 359 ms
17,116 KB
testcase_28 AC 356 ms
16,672 KB
testcase_29 AC 359 ms
16,736 KB
testcase_30 AC 357 ms
16,688 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

/**
 * @title Lazy segment tree
 * @docs lazy_segment_tree.md
 */
template <typename Monoid>
class LazySegmentTree{
  using value_type_get = typename Monoid::value_type_get;
  using value_type_update = typename Monoid::value_type_update;
  
  const int depth, size, hsize;
  std::vector<value_type_get> data;
  std::vector<value_type_update> lazy;

  inline void propagate(int i){
    if(lazy[i] == Monoid::id_update()) return;
    if(i < hsize){
      lazy[i << 1 | 0] = Monoid::op_update(lazy[i], lazy[i << 1 | 0]);
      lazy[i << 1 | 1] = Monoid::op_update(lazy[i], lazy[i << 1 | 1]);
    }
    int len = hsize >> (31 - __builtin_clz(i));
    data[i] = Monoid::op(data[i], lazy[i], len);
    lazy[i] = Monoid::id_update();
  }

  inline value_type_get update_aux(int i, int l, int r, int s, int t, const value_type_update &x){
    propagate(i);
    if(r <= s || t <= l) return data[i];
    else if(s <= l && r <= t){
      lazy[i] = Monoid::op_update(x, lazy[i]);
      propagate(i);
      return data[i];
    }
    else return data[i] = Monoid::op_get(update_aux(i << 1 | 0, l, (l+r) / 2, s, t, x), update_aux(i << 1 | 1, (l+r) / 2, r, s, t, x));
  }
  
  inline value_type_get get_aux(int i, int l, int r, int x, int y){
    propagate(i);
    if(r <= x || y <= l) return Monoid::id_get();
    else if(x <= l && r <= y) return data[i];
    else return Monoid::op_get(get_aux(i << 1 | 0, l, (l+r) / 2, x, y), get_aux(i << 1 | 1, (l+r) / 2, r, x, y));
  }

public:
  LazySegmentTree(){}
  LazySegmentTree(int n):
    depth(n > 1 ? 32-__builtin_clz(n-1) + 1 : 1),
    size(1 << depth),
    hsize(size / 2),
    data(size, Monoid::id_get()),
    lazy(size, Monoid::id_update())
  {}

  inline void update(int l, int r, const value_type_update &x){update_aux(1, 0, hsize, l, r, x);}
  inline void update_at(int i, const value_type_update &x){update(i, i+1, x);}
  inline value_type_get get(int l, int r){return get_aux(1, 0, hsize, l, r);}
  inline value_type_get at(int i){return get(i, i+1);}

  template <typename T>
  inline void init(const T &val){
    init_with_vector(std::vector<T>(hsize, val));
  }

  template <typename T>
  inline void init_with_vector(const std::vector<T> &val){
    data.assign(size, Monoid::id_get());
    lazy.assign(size, Monoid::id_update());
    for(int i = 0; i < (int)val.size(); ++i) data[hsize + i] = val[i];
    for(int i = hsize-1; i > 0; --i) data[i] = Monoid::op_get(data[i << 1 | 0], data[i << 1 | 1]);
  }
};

template <typename T>
struct AddSquareSum{
  using value_type_get = std::pair<T, T>;
  using value_type_update = T;

  static value_type_get id_get(){
    return std::make_pair(0, 0);
  }

  static value_type_update id_update(){
    return 0;
  }

  static value_type_get op_get(const value_type_get &a, const value_type_get &b){
    return std::make_pair(a.first + b.first, a.second + b.second);
  }

  static value_type_update op_update(const value_type_update &a, const value_type_update &b){
    return a + b;
  }
  
  static value_type_get op(const value_type_get &a, const value_type_update &b, int len){
    return std::make_pair(a.first + b * len, a.second + b * (2 * a.first + b * len));
  }
};




int main(){
  int N; std::cin >> N;

  std::vector<int64_t> A(N);
  for(int i = 0; i < N; ++i) std::cin >> A[i];

  LazySegmentTree<AddSquareSum<int64_t>> seg(N);
  for(int i = 0; i < N; ++i) seg.update_at(i, A[i]);

  int Q; std::cin >> Q;

  while(Q--){
    int type; std::cin >> type;

    if(type == 1){
      int l, r, x; std::cin >> l >> r >> x;

      seg.update(l-1, r, x);
    }else{
      int l, r; std::cin >> l >> r;

      std::cout << std::get<1>(seg.get(l-1, r)) << "\n";
    }
  }

  return 0;
}
0