結果

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

ソースコード

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

#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;
// propagate
if (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 data
dat[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 data
dat[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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0