結果
問題 | No.1099 Range Square Sum |
ユーザー |
![]() |
提出日時 | 2024-06-10 17:18:51 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 371 ms / 2,000 ms |
コード長 | 1,303 bytes |
コンパイル時間 | 4,730 ms |
コンパイル使用メモリ | 257,360 KB |
最終ジャッジ日時 | 2025-02-21 21:04:30 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>using namespace std;using namespace atcoder;struct S {long long sum2, sum1, size;S(long long sum2_, long long sum1_, long long size_) :sum2(sum2_), sum1(sum1_), size(size_) {}};S op(S l, S r) {S res(l.sum2 + r.sum2, l.sum1 + r.sum1, l.size + r.size);return res;}S e() {S res(0LL, 0LL, 1LL);return res;}S mapping(long long x, S s) {S res(s.sum2 + 2LL * x * s.sum1 + s.size * x * x, s.sum1 + s.size * x, s.size);return res;}long long composition(long long f, long long g) {return f + g;}long long id() {return 0LL;}int main() {int n;cin >> n;vector<long long> a(n);for (int i = 0; i < n; i++) {cin >> a[i];}lazy_segtree<S, op, e, long long, mapping, composition, id> seg(n);for (int i = 0; i < n; i++) {seg.set(i, {a[i] * a[i], a[i], 1LL});}int q;cin >> q;while (q--) {int t;cin >> t;if (t == 1) {int l, r;long long x;cin >> l >> r >> x;l--;seg.apply(l, r, x);} else {int l, r;cin >> l >> r;l--;cout << seg.prod(l, r).sum2 << endl;}}}