結果
問題 | No.1099 Range Square Sum |
ユーザー |
|
提出日時 | 2020-08-18 12:02:30 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 419 ms / 2,000 ms |
コード長 | 4,499 bytes |
コンパイル時間 | 1,187 ms |
コンパイル使用メモリ | 96,196 KB |
最終ジャッジ日時 | 2025-01-13 03:00:07 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 30 |
ソースコード
#include <iostream>#include <vector>#include <functional>template <class T, class E>struct LazySegmentTree {using DMerger = std::function<T(T, T)>;using OMerger = std::function<E(E, E)>;using Applier = std::function<T(T, E, int)>;int length;T d_unit;E o_unit;std::vector<T> dat;std::vector<E> ope;DMerger dmerge;OMerger omerge;Applier app;explicit LazySegmentTree(int n,T d_unit, E o_unit,DMerger dmerge,OMerger omerge,Applier app): length(1),d_unit(d_unit),o_unit(o_unit),dmerge(dmerge),omerge(omerge),app(app) {while (length < n) length <<= 1;dat.assign(length * 2, d_unit);ope.assign(length * 2, o_unit);}template <class Container>explicit LazySegmentTree(const Container& elems,T d_unit, E o_unit,DMerger dmerge,OMerger omerge,Applier app): length(1),d_unit(d_unit),o_unit(o_unit),dmerge(dmerge),omerge(omerge),app(app) {int n = elems.size();while (length < n) length <<= 1;dat.assign(length * 2, d_unit);ope.assign(length * 2, o_unit);std::copy(elems.begin(), elems.end(), dat.begin() + length);for (int nidx = length - 1; nidx >= 1; --nidx) {T vl = dat[nidx * 2 + 0];T vr = dat[nidx * 2 + 1];dat[nidx] = dmerge(vl, vr);}}void propagate(int nidx, int len) {if (ope[nidx] == o_unit) return;// propagateif (len > 1) {ope[nidx * 2 + 0] = omerge(ope[nidx * 2 + 0], ope[nidx]);ope[nidx * 2 + 1] = omerge(ope[nidx * 2 + 1], ope[nidx]);}// update datadat[nidx] = app(dat[nidx], ope[nidx], len);ope[nidx] = o_unit;}void update(int ql, int qr, E e, int nidx, int nl, int nr) {propagate(nidx, nr - nl);if (nr <= ql || qr <= nl) return;if (ql <= nl && nr <= qr) {ope[nidx] = omerge(ope[nidx], e);propagate(nidx, nr - nl);return;}int nm = (nl + nr) / 2;update(ql, qr, e, nidx * 2 + 0, nl, nm);update(ql, qr, e, nidx * 2 + 1, nm, nr);// update datadat[nidx] = dmerge(dat[nidx * 2 + 0], dat[nidx * 2 + 1]);}void update(int ql, int qr, E e) { return update(ql, qr, e, 1, 0, length); }T fold(int ql, int qr, int nidx, int nl, int nr) {propagate(nidx, nr - nl);if (nr <= ql || qr <= nl) return d_unit;if (ql <= nl && nr <= qr) return dat[nidx];int nm = (nl + nr) / 2;T vl = fold(ql, qr, nidx * 2 + 0, nl, nm);T vr = fold(ql, qr, nidx * 2 + 1, nm, nr);return dmerge(vl, vr);}T fold(int ql, int qr) { return fold(ql, qr, 1, 0, length); }T get(int idx) { return fold(idx, idx + 1); }T fold_all() { return fold(0, length); }};using lint = long long;struct Node {lint sum, sqsum;Node() : sum(0), sqsum(0) {}Node(lint sum, lint sqsum) : sum(sum), sqsum(sqsum) {}};void solve() {int n;std::cin >> n;LazySegmentTree<Node, lint>seg(n, Node(), 0,[](Node a, Node b) { return Node(a.sum + b.sum,a.sqsum + b.sqsum); },[](lint e, lint f) { return e + f; },[](Node a, lint e, int k) { return Node(a.sum + e * k,a.sqsum + a.sum * e * 2 + e * e * k); });for (int i = 0; i < n; ++i) {lint a;std::cin >> a;seg.update(i, i + 1, a);}int q;std::cin >> q;while (q--) {int t, l, r;std::cin >> t >> l >> r;--l;switch (t) {case 1: {lint x;std::cin >> x;seg.update(l, r, x);break;}case 2: {std::cout << seg.fold(l, r).sqsum << "\n";break;}}}}int main() {std::cin.tie(nullptr);std::ios::sync_with_stdio(false);solve();return 0;}