結果
問題 | No.1099 Range Square Sum |
ユーザー |
|
提出日時 | 2020-06-26 22:14:27 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 170 ms / 2,000 ms |
コード長 | 4,748 bytes |
コンパイル時間 | 1,754 ms |
コンパイル使用メモリ | 176,464 KB |
実行使用メモリ | 19,260 KB |
最終ジャッジ日時 | 2024-07-04 21:49:04 |
合計ジャッジ時間 | 4,991 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;using P = pair<ll, ll>;constexpr char newl = '\n';// [Related]: monoid_op// 参考: http://kazuma8128.hatenablog.com/entry/2017/12/29/081929template <class MonoidOp>struct LazySegmentTree {using Tm = typename MonoidOp::Tm;using To = typename MonoidOp::To;int n;int h;vector<Tm> data;vector<To> lazy;LazySegmentTree() {}LazySegmentTree(int size, Tm initial_data_value = MonoidOp::unit()) {n = 1;h = 0;while (n < size) {h++;n <<= 1;}data.assign((n << 1), initial_data_value);lazy.assign((n << 1), MonoidOp::op_unit());if (initial_data_value != MonoidOp::unit()) {for (int i = n - 1; i > 0; i--) data[i] = MonoidOp::merge(data[(i << 1)], data[(i << 1) + 1]);}}LazySegmentTree(const vector<Tm>& v) {int size = v.size();n = 1;h = 0;while (n < size) {h++;n <<= 1;}data.assign((n << 1), MonoidOp::unit());lazy.assign((n << 1), MonoidOp::op_unit());for (int i = 0; i < size; i++) data[i + n] = v[i];for (int i = n - 1; i > 0; i--) data[i] = MonoidOp::merge(data[(i << 1)], data[(i << 1) + 1]);}// https://komiyam.hatenadiary.org/entry/20131202/1385992406inline int getSegLen(int k) {return n / (1 << (31 - __builtin_clz(k)));}Tm getLeaf(int k) {return query(k, k + 1);}void push(int k) {if (lazy[k] == MonoidOp::op_unit()) return;int seg_len = getSegLen(k);data[k] = MonoidOp::apply(data[k], lazy[k], seg_len);if (seg_len > 1) {lazy[(k << 1)] = MonoidOp::op_merge(lazy[(k << 1)], lazy[k]);lazy[(k << 1) + 1] = MonoidOp::op_merge(lazy[(k << 1) + 1], lazy[k]);}lazy[k] = MonoidOp::op_unit();}void update(int k) {Tm vl = MonoidOp::apply(data[(k << 1)], lazy[(k << 1)], getSegLen(k << 1));Tm vr = MonoidOp::apply(data[(k << 1) + 1], lazy[(k << 1) + 1], getSegLen((k << 1) + 1));data[k] = MonoidOp::merge(vl, vr);}//区間[a, b)に対する更新void update(int a, int b, To x) {a += n, b += n - 1;for (int i = h; i > 0; i--) {push(a >> i);push(b >> i);}for (int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {if (l & 1) lazy[l] = MonoidOp::op_merge(lazy[l], x), l++;if (r & 1) --r, lazy[r] = MonoidOp::op_merge(lazy[r], x);}while (a >>= 1, b >>= 1, a) {if (lazy[a] == MonoidOp::op_unit()) update(a);if (lazy[b] == MonoidOp::op_unit()) update(b);}}//区間[a, b)に対するクエリに答えるTm query(int a, int b) {a += n, b += n - 1;for (int i = h; i > 0; i--) {push(a >> i);push(b >> i);}Tm vl = MonoidOp::unit(), vr = MonoidOp::unit();for (int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {if (l & 1) {vl = MonoidOp::merge(vl, MonoidOp::apply(data[l], lazy[l], getSegLen(l)));l++;}if (r & 1) {--r;vr = MonoidOp::merge(MonoidOp::apply(data[r], lazy[r], getSegLen(r)), vr);}}return MonoidOp::merge(vl, vr);}};template<class U = P, class V = ll>struct RangeSumAdd {using Tm = U;using To = V;static Tm merge(const Tm& x, const Tm& y) {return Tm(x.first + y.first, x.second + y.second);}static To op_merge(const To& x, const To& y) {return x + y;}static Tm apply(const Tm& vm, const To& vo, int seg_len) {return Tm(vm.first + vo * seg_len, vm.second + vm.first * vo * 2 + vo * vo * seg_len);}static constexpr Tm unit() { return Tm(0, 0); }static constexpr To op_unit() { return To(0); }};int main() {cin.tie(nullptr);ios::sync_with_stdio(false);int n;cin >> n;vector<P> v;for (int i = 0; i < n; i++) {ll a;cin >> a;v.emplace_back(a, a * a);}LazySegmentTree< RangeSumAdd<> > st(v);int q;cin >> q;for (int i = 0; i < q; i++) {int com;cin >> com;if (com == 1) {int l, r;ll x;cin >> l >> r >> x;--l;st.update(l, r, x);} else {int l, r;cin >> l >> r;--l;cout << st.query(l, r).second << newl;}}return 0;}