結果
問題 | No.1099 Range Square Sum |
ユーザー |
|
提出日時 | 2020-08-18 11:57:29 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,590 bytes |
コンパイル時間 | 1,276 ms |
コンパイル使用メモリ | 95,408 KB |
最終ジャッジ日時 | 2025-01-13 02:59:45 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 2 WA * 28 |
ソースコード
#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 {__int128_t sum, diff;Node() : sum(0), diff(0) {}Node(lint sum, lint diff) : sum(sum), diff(diff) {}};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.diff + b.diff + a.sum * b.sum); },[](lint e, lint f) { return e + f; },[](Node a, lint e, int k) { return Node(a.sum + e * k,a.diff + a.sum * e * (k - 1) + e * k * (k - 1) / 2); });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: {auto res = seg.fold(l, r);std::cout << lint(res.sum * res.sum - res.diff * 2) << "\n";break;}}}}int main() {std::cin.tie(nullptr);std::ios::sync_with_stdio(false);solve();return 0;}