結果
問題 | No.1099 Range Square Sum |
ユーザー |
|
提出日時 | 2020-09-29 01:16:07 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 232 ms / 2,000 ms |
コード長 | 18,422 bytes |
コンパイル時間 | 1,014 ms |
コンパイル使用メモリ | 97,564 KB |
最終ジャッジ日時 | 2025-01-14 23:21:01 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 30 |
ソースコード
#include <iostream>#include <iomanip>#include <algorithm>#include <array>#include <cassert>#include <optional>#include <utility>#include <vector>template <class InputIterator>std::ostream& range_output(std::ostream& os_arg, InputIterator first_arg, InputIterator last_arg){ if(first_arg != last_arg){ do{ os_arg <<*(first_arg++); if(first_arg == last_arg) break; os_arg << ' '; } while(true); } return os_arg; }template <class Tp> std::ostream& operator << (std::ostream& os_arg, const std::vector<Tp>& arr_arg){ return range_output(os_arg, arr_arg.cbegin(),arr_arg.cend()); }template <class Tp, std::size_t Size> std::ostream& operator << (std::ostream& os_arg, const std::array<Tp, Size>& arr_arg){ return range_output(os_arg, arr_arg.cbegin(), arr_arg.cend()); }template <class S, class T> std::ostream& operator << (std::ostream& os_arg, const std::pair<S, T>& pair_arg){ return os_arg << '(' << pair_arg.first<< ", " << pair_arg.second << ')'; }#ifndef ONLINE_JUDGEtemplate <typename Head> void dump_out(Head head_arg){ std::cerr << head_arg << '\n'; }template <typename Head, typename... Tail>void dump_out(Head head_arg, Tail... tail_args){ std::cerr << head_arg << ", "; dump_out(tail_args...); }#define dump(...) do { std::cerr << "[in line " << __LINE__ << "] " << #__VA_ARGS__ << " : "; dump_out(__VA_ARGS__); } while(false)#else#define dump(...) (void(0))#endif// @ 遅延伝搬セグメント木 (データ構造)// * 区間更新, 区間取得 が O(logN) で達成可能である// 下のマクロは 区間の「位置」 [L, R) の情報を用いるかのマクロ// if : true -> 用いる : merge に 区間 [L, R) (0-indexed) の情報を用いる// if : false -> 用いない : merge に 区間幅 N を用いることができる#define USE_RANGE_INFO_FOR_LAZY_SEGTREE false// ''''''''''''''''''''''''''''''''''''''''''''''''''''''''''// struct monoid_lazy_segment_tree{// using value_type = ; // データの型// using lazy_type = ; // 遅延評価作用素の型// inline static constexpr value_type identity_element = 0; // データの単位元// // データ型の演算 (クエリの畳み込み和の演算) : 他ライブラリでは f などで書かれている// static value_type operation(const value_type& x, const value_type& y){// return ;// }// #if USE_RANGE_INFO_FOR_LAZY_SEGTREE// // 遅延評価を実際に行う演算 : (更新(評価)されるデータ型の値, 遅延作用素, その区間 [L, R)) → 新しく評価するデータの値// // ※※※ 配列参照外に注意する必要はない ※※※// static value_type merge(const value_type& x, const lazy_type& y, const int L, const int R){// return ;// }// #else// // 遅延評価を実際に行う演算 : (更新(評価)されるデータ型の値, 遅延作用素, その区間幅 N → 新しく評価するデータの値// static value_type merge(const value_type& x, const lazy_type& y, const int N){// return ;// }// #endif// // 遅延作用素の伝搬 (古い作用素, 新しい作用素) → (作用素)// static lazy_type propagate(const lazy_type& x, const lazy_type& y){// return ;// }// };// ''''''''''''''''''''''''''''''''''''''''''''''''''''''''''template <class monoid_lazy_segment_tree> class LazySegmentTree{private:using element_t = typename monoid_lazy_segment_tree::value_type;using lazy_t = typename monoid_lazy_segment_tree::lazy_type;using lazy_opt_t = std::optional<lazy_t>;const int arr_len; // 扱う配列の長さ nconst int height; // セグメント木の高さ : 要素数 2^k の kconst int length; // セグメント木の要素数 : 2^k (dataの数は 2 * 2^k)std::vector<element_t> data; // 要素の部分std::vector<lazy_opt_t> lazy; // 遅延評価部分// セグメント木に必要な高さを計算する補助関数static int make_height(const int n){int res = 0; for(int len = 1; len < n; ++res, len *= 2);return res;}// 葉である頂点 x から 根に向かってボトムアップに 要素本体 (data) の値を lazy を元に更新していく関数inline void calculateData(int x){#if USE_RANGE_INFO_FOR_LAZY_SEGTREEfor(int shift = 0, len = 1; x /= 2; ++shift, len *= 2){const int c1 = 2 * x, c2 = c1 + 1;const int cl1 = (c1 ^ (1 << (height - shift))) << shift, cl2 = cl1 + len;// 左端が arr_len より大きい区間は更新されない(lazyはstd::nullopt) → 右端のみを arr_len に丸めるdata[x] = monoid_lazy_segment_tree::operation(lazy[c1] ? monoid_lazy_segment_tree::merge(data[c1], *lazy[c1], cl1, std::min(cl2, arr_len)) : data[c1],lazy[c2] ? monoid_lazy_segment_tree::merge(data[c2], *lazy[c2], cl2, std::min(cl2 + len, arr_len)) : data[c2]);}#elsefor(int len = 1; x /= 2; len *= 2){const int c1 = 2 * x, c2 = c1 + 1;data[x] = monoid_lazy_segment_tree::operation(lazy[c1] ? monoid_lazy_segment_tree::merge(data[c1], *lazy[c1], len) : data[c1],lazy[c2] ? monoid_lazy_segment_tree::merge(data[c2], *lazy[c2], len) : data[c2]);}#endif}// 葉である頂点 x に向かって根からトップダウンに遅延評価部(lazy)を伝搬させていく関数inline void propagate(int x){for(int shift = height, len = 1 << shift; shift ; --shift, len /= 2){const int idx = x >> shift;if(lazy[idx]){const int idx1 = 2 * idx;lazy[idx1] = lazy[idx1] ? lazy_opt_t(monoid_lazy_segment_tree::propagate(*lazy[idx1], *lazy[idx])) : lazy[idx];const int idx2 = 2 * idx + 1;lazy[idx2] = lazy[idx2] ? lazy_opt_t(monoid_lazy_segment_tree::propagate(*lazy[idx2], *lazy[idx])) : lazy[idx];#if USE_RANGE_INFO_FOR_LAZY_SEGTREEconst int ldx = (idx ^ (1 << (height - shift))) << shift;// 左端が arr_len より大きい区間は更新されない(lazyはstd::nullopt) → 右端のみを arr_len に丸めるdata[idx] = monoid_lazy_segment_tree::merge(data[idx], *lazy[idx], ldx, std::min(ldx + len, arr_len));#elsedata[idx] = monoid_lazy_segment_tree::merge(data[idx], *lazy[idx], len);#endiflazy[idx] = std::nullopt;}}#if USE_RANGE_INFO_FOR_LAZY_SEGTREEif(lazy[x]){ data[x] = monoid_lazy_segment_tree::merge(data[x], *lazy[x], x - length, x - length + 1); lazy[x] = std::nullopt; }#elseif(lazy[x]){ data[x] = monoid_lazy_segment_tree::merge(data[x], *lazy[x], 1); lazy[x] = std::nullopt; }#endif}public:// コンストラクタLazySegmentTree(const int len): arr_len(len), height(make_height(arr_len)), length(1 << height){data.assign(2 * length, monoid_lazy_segment_tree::identity_element);lazy.assign(2 * length, std::nullopt);}LazySegmentTree(const int len, const element_t& init_value): arr_len(len), height(make_height(arr_len)), length(1 << height){data.resize(2 * length);std::fill(data.begin() + length, data.begin() + length + len, init_value);std::fill(data.begin() + length + len, data.end(), monoid_lazy_segment_tree::identity_element);for(int idx = length - 1; idx > 0; --idx) data[idx] = monoid_lazy_segment_tree::operation(data[2 * idx], data[2 * idx + 1]);lazy.assign(2 * length, std::nullopt);}LazySegmentTree(const std::vector<element_t>& A): arr_len(A.size()), height(make_height(arr_len)), length(1 << height){lazy.assign(2 * length, std::nullopt);data.resize(2 * length); std::copy(A.begin(), A.end(), data.begin() + length);std::fill(data.begin() + length + A.size(), data.end(), monoid_lazy_segment_tree::identity_element);for(int idx = length - 1; idx > 0; --idx) data[idx] = monoid_lazy_segment_tree::operation(data[2 * idx], data[2 * idx + 1]);}template <class InputIterator>LazySegmentTree(InputIterator first, InputIterator last):arr_len(std::distance(first, last)), height(make_height(arr_len)), length(1 << height){lazy.assign(2 * length, std::nullopt);data.resize(2 * length); std::copy(first, last, data.begin() + length);std::fill(data.begin() + length + arr_len, data.end(), monoid_lazy_segment_tree::identity_element);for(int idx = length - 1; idx; --idx) data[idx] = monoid_lazy_segment_tree::operation(data[2 * idx], data[2 * idx + 1]);}// @ 半開区間 [l, r) (0-indexed) に作用素 val を作用させる関数 : 計算量 O(logN)inline void update_range(int l, int r, const lazy_t& val){assert(0 <= l and l <= r and r <= arr_len);if(l == r) return ;propagate(l += length); propagate(r += length - 1);for(int li = l, ri = r + 1; li < ri; li >>= 1, ri >>= 1){if(li & 1){ lazy[li] = lazy[li] ? monoid_lazy_segment_tree::propagate(*lazy[li], val) : val; li++; }if(ri & 1){ --ri; lazy[ri] = lazy[ri] ? monoid_lazy_segment_tree::propagate(*lazy[ri], val) : val; }}calculateData(l); calculateData(r);}// @ 1点 index (0-indexed) に作用素 val を作用させる関数inline void update_at(int index, const lazy_t& val){assert(0 <= index and index < arr_len);propagate(index += length);#if USE_RANGE_INFO_FOR_LAZY_SEGTREEdata[index] = monoid_lazy_segment_tree::merge(data[index], val, index - length, index - length + 1);#elsedata[index] = monoid_lazy_segment_tree::merge(data[index], val, 1);#endifcalculateData(index);}// @ 1点 index (0-indexed) に直接, 値 val を「代入」する関数inline void assign_at(int index, const element_t& val){assert(0 <= index and index < arr_len);propagate(index += length);data[index] = val;calculateData(index);}// @ 半開区間 [l, r) (0-indexed) 上の畳み込み和 al * al+1 * ... * ar-1 を求める関数inline element_t fold_range(int l, int r){assert(0 <= l and l <= r and r <= arr_len);if(l == r) return monoid_lazy_segment_tree::identity_element;propagate(l += length); propagate((r += length) - 1);element_t vl = monoid_lazy_segment_tree::identity_element, vr = monoid_lazy_segment_tree::identity_element;#if USE_RANGE_INFO_FOR_LAZY_SEGTREEfor(int shift = 0, len = 1; l < r ; l /= 2, r /= 2, len *= 2, ++shift){if(l & 1){if(lazy[l]){const int ll = (l ^ (1 << (height - shift))) << shift;vl = monoid_lazy_segment_tree::operation(vl, monoid_lazy_segment_tree::merge(data[l], *lazy[l], ll, ll + len));}else vl = monoid_lazy_segment_tree::operation(vl, data[l]);l++;}if(r & 1){--r;if(lazy[r]){const int rl = (r ^ (1 << (height - shift))) << shift;vr = monoid_lazy_segment_tree::operation(monoid_lazy_segment_tree::merge(data[r], *lazy[r], rl, rl + len), vr);}else vr = monoid_lazy_segment_tree::operation(data[r], vr);}}#elsefor(int len = 1; l < r; l /= 2, r /= 2, len *= 2){if(l & 1){vl = monoid_lazy_segment_tree::operation( vl, lazy[l] ? monoid_lazy_segment_tree::merge(data[l], *lazy[l], len) : data[l] ); l++;}if(r & 1){--r; vr = monoid_lazy_segment_tree::operation(lazy[r] ? monoid_lazy_segment_tree::merge(data[r], *lazy[r], len) : data[r], vr);}}#endifreturn monoid_lazy_segment_tree::operation(vl, vr);}// @ 全区間の畳み込み和を求める関数 : O(1)inline element_t fold_all(void) const { return data[1]; }// @ 1点 index (0-indexed) の値を得る関数 : O(logN)inline element_t fold_at(int index){ propagate(index += length); return data[index]; }// @ 1点 index (0-indexed) の値を得る関数 : O(logN)inline const element_t& operator [](int index){ propagate(index += length); return data[index]; }// @ セグ木上の二分探索(右側) : 初めて comp(∑_[l, r) ai) が初めて true となる右端 r を返す (存在しない場合, -1 を返す)// 仮定 ; 比較関数に対して false, false, ..., true, ... という単調性があるtemplate <class Compare_t> int right_search(int l, Compare_t comp){assert(0 <= l and l <= arr_len);if(comp(monoid_lazy_segment_tree::identity_element)) return l;if(l == arr_len) return -1;propagate(l += length);element_t l_sum = monoid_lazy_segment_tree::identity_element;do {int shift = 0, len = 1;for(; l % 2 == 0; l /= 2, ++shift, len *= 2);#if USE_RANGE_INFO_FOR_LAZY_SEGTREEconst int ll = (l ^ (1 << (height - shift))) << shift; if(arr_len <= ll) return -1;const element_t tmp_val = monoid_lazy_segment_tree::operation(l_sum, lazy[l] ? monoid_lazy_segment_tree::merge(data[l], *lazy[l], ll, std::min(arr_len, ll + len)) : data[l]);#elseconst element_t tmp_val = monoid_lazy_segment_tree::operation( l_sum, lazy[l] ? monoid_lazy_segment_tree::merge(data[l], *lazy[l], len) :data[l] );#endifif(comp(tmp_val)){while(l < length){if(lazy[l]){const int idx1 = 2 * l;lazy[idx1] = lazy[idx1] ? lazy_opt_t(monoid_lazy_segment_tree::propagate(*lazy[idx1], *lazy[l])) : lazy[l];const int idx2 = 2 * l + 1;lazy[idx2] = lazy[idx2] ? lazy_opt_t(monoid_lazy_segment_tree::propagate(*lazy[idx2], *lazy[l])) : lazy[l];#if USE_RANGE_INFO_FOR_LAZY_SEGTREEconst int lll = (l ^ (1 << (height - shift))) << shift;if(arr_len <= lll) return -1;// 左端が arr_len より大きい区間は更新されない(lazyはstd::nullopt) → 右端のみを arr_len に丸めるdata[l] = monoid_lazy_segment_tree::merge(data[l], *lazy[l], lll, std::min(lll + len, arr_len));#elsedata[l] = monoid_lazy_segment_tree::merge(data[l], *lazy[l], len);#endiflazy[l] = std::nullopt;}l *= 2; len *= 2; --shift;#if USE_RANGE_INFO_FOR_LAZY_SEGTREEconst int lll = (l ^ (1 << (height - shift))) << shift; if(arr_len <= lll) return -1;const element_t tmp_val2 = monoid_lazy_segment_tree::operation(l_sum, lazy[l] ? monoid_lazy_segment_tree::merge(data[l], *lazy[l], lll, std::min(arr_len, lll + len)) : data[l]);#elseconst element_t tmp_val2 = monoid_lazy_segment_tree::operation( l_sum, lazy[l] ? monoid_lazy_segment_tree::merge(data[l],*lazy[l], len) : data[l] );#endifif(not comp(tmp_val2)){ l_sum = tmp_val2; ++l; }}return l - length + 1;}l_sum = tmp_val;l++;} while ((l & -l) != l);return -1;}template <bool (*comp)(const element_t&)> int right_search(int l){return right_search(l, [](const element_t& x){ return comp(x); });}};// ''''''''''''''''''''''''''''''''''''''''''''''''''''''''''struct monoid_lazy_segment_tree{using value_type = std::pair<long long int, long long int>; // データの型using lazy_type = long long int; // 遅延評価作用素の型inline static const value_type identity_element = value_type(0, 0); // データの単位元// データ型の演算 (クエリの畳み込み和の演算) : 他ライブラリでは f などで書かれているstatic value_type operation(const value_type& x, const value_type& y){return value_type(x.first + y.first, x.second + y.second);}#if USE_RANGE_INFO_FOR_LAZY_SEGTREE// 遅延評価を実際に行う演算 : (更新(評価)されるデータ型の値, 遅延作用素, その区間 [L, R)) → 新しく評価するデータの値// ※※※ 配列参照外に注意する必要はない ※※※ (0 ≤ L ≤ R ≤ n)static value_type merge(const value_type& x, const lazy_type& y, const int L, const int R){return ;}#else// 遅延評価を実際に行う演算 : (更新(評価)されるデータ型の値, 遅延作用素, その区間幅 N → 新しく評価するデータの値static value_type merge(const value_type& x, const lazy_type& y, const int N){return value_type(x.first + y * N, x.second + 2 * y * x.first + y * y * N);}#endif// 遅延作用素の伝搬 (古い作用素, 新しい作用素) → (作用素)static lazy_type propagate(const lazy_type& x, const lazy_type& y){return x + y;}};int main(void){std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false);std::cout << std::fixed << std::setprecision(16);int n; std::cin >> n;std::vector<std::pair<long long int, long long int>> A(n);for(int i = 0; i < n; ++i){std::cin >> A[i].first; A[i].second = A[i].first * A[i].first;}LazySegmentTree<monoid_lazy_segment_tree> LST(A.cbegin(), A.cend());int q; std::cin >> q;while(q--){char c; int l, r; std::cin >> c >> l >> r; --l;if(c == '1'){int x; std::cin >> x; LST.update_range(l, r, x);}else std::cout << LST.fold_range(l, r).second << std::endl;}return 0;}