結果

問題 No.1099 Range Square Sum
コンテスト
ユーザー Haar
提出日時 2020-06-27 20:23:11
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,502 ms / 2,000 ms
コード長 3,701 bytes
コンパイル時間 3,109 ms
コンパイル使用メモリ 200,288 KB
最終ジャッジ日時 2025-01-11 13:02:43
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

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