結果

問題 No.1099 Range Square Sum
ユーザー WarToks
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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_JUDGE
template <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; // n
const int height; // : 2^k k
const 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_SEGTREE
for(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 (lazystd::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]
);
}
#else
for(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_SEGTREE
const int ldx = (idx ^ (1 << (height - shift))) << shift;
// arr_len (lazystd::nullopt) → arr_len
data[idx] = monoid_lazy_segment_tree::merge(data[idx], *lazy[idx], ldx, std::min(ldx + len, arr_len));
#else
data[idx] = monoid_lazy_segment_tree::merge(data[idx], *lazy[idx], len);
#endif
lazy[idx] = std::nullopt;
}
}
#if USE_RANGE_INFO_FOR_LAZY_SEGTREE
if(lazy[x]){ data[x] = monoid_lazy_segment_tree::merge(data[x], *lazy[x], x - length, x - length + 1); lazy[x] = std::nullopt; }
#else
if(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_SEGTREE
data[index] = monoid_lazy_segment_tree::merge(data[index], val, index - length, index - length + 1);
#else
data[index] = monoid_lazy_segment_tree::merge(data[index], val, 1);
#endif
calculateData(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_SEGTREE
for(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);
}
}
#else
for(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);
}
}
#endif
return 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_SEGTREE
const 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]
);
#else
const 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] );
#endif
if(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_SEGTREE
const int lll = (l ^ (1 << (height - shift))) << shift;
if(arr_len <= lll) return -1;
// arr_len (lazystd::nullopt) → arr_len
data[l] = monoid_lazy_segment_tree::merge(data[l], *lazy[l], lll, std::min(lll + len, arr_len));
#else
data[l] = monoid_lazy_segment_tree::merge(data[l], *lazy[l], len);
#endif
lazy[l] = std::nullopt;
}
l *= 2; len *= 2; --shift;
#if USE_RANGE_INFO_FOR_LAZY_SEGTREE
const 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]
);
#else
const 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] );
#endif
if(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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0