#504239 (C++17) No.1099 Range Square Sum

• 問題: No.1099 Range Square Sum
• ユーザー: Haar
• 提出日時: 2020-06-27 20:23:11
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 449 ms / 2,000 ms
• コード長: 3,701 bytes
• コンパイル時間: 2,374 ms
• コンパイル使用メモリ: 208,636 KB
• 実行使用メモリ: 17,152 KB
• 最終ジャッジ日時: 2024-07-05 20:58:33
• 合計ジャッジ時間: 8,203 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	1 ms; 5,376 KB
testcase_07	AC	1 ms; 5,376 KB
testcase_08	AC	1 ms; 5,376 KB
testcase_09	AC	2 ms; 5,376 KB
testcase_10	AC	2 ms; 5,376 KB
testcase_11	AC	5 ms; 5,376 KB
testcase_12	AC	4 ms; 5,376 KB
testcase_13	AC	4 ms; 5,376 KB
testcase_14	AC	4 ms; 5,376 KB
testcase_15	AC	4 ms; 5,376 KB
testcase_16	AC	5 ms; 5,376 KB
testcase_17	AC	4 ms; 5,376 KB
testcase_18	AC	5 ms; 5,376 KB
testcase_19	AC	4 ms; 5,376 KB
testcase_20	AC	4 ms; 5,376 KB
testcase_21	AC	430 ms; 17,024 KB
testcase_22	AC	449 ms; 17,024 KB
testcase_23	AC	432 ms; 17,024 KB
testcase_24	AC	429 ms; 17,024 KB
testcase_25	AC	439 ms; 17,024 KB
testcase_26	AC	370 ms; 17,152 KB
testcase_27	AC	371 ms; 17,152 KB
testcase_28	AC	377 ms; 17,024 KB
testcase_29	AC	364 ms; 17,024 KB
testcase_30	AC	370 ms; 17,024 KB

ソースコード

#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;
}