結果
問題 | No.1099 Range Square Sum |
ユーザー |
|
提出日時 | 2024-03-06 18:15:45 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 267 ms / 2,000 ms |
コード長 | 1,074 bytes |
コンパイル時間 | 4,819 ms |
コンパイル使用メモリ | 316,656 KB |
実行使用メモリ | 23,052 KB |
最終ジャッジ日時 | 2024-09-29 18:31:55 |
合計ジャッジ時間 | 8,901 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>#if __has_include(<atcoder/all>)#include <atcoder/all>using namespace atcoder;#endif#define rep(i, n) for (int i = 0; i < (n); ++i)using namespace std;using ll = long long;struct S {ll x, x2;int size;S(ll x=0, ll x2=0, int size=0): x(x), x2(x2), size(size) {}};S op(S a, S b) { return S(a.x+b.x, a.x2+b.x2, a.size+b.size); }S e() { return S(); }S mapping(ll f, S s) { return S(s.x + f*s.size, s.x2 + 2*f*s.x + f*f*s.size, s.size); }ll composition(ll g, ll f) { return f+g; }ll id() { return 0; }int main() {int n;cin >> n;vector<S> a;rep(i, n) {ll x; cin >> x;a.emplace_back(x, x*x, 1);}int q;cin >> q;lazy_segtree<S, op, e, ll, mapping, composition, id> t(a);rep(qi, q) {int type, l, r;cin >> type >> l >> r;--l;if (type == 1) {int x;cin >> x;t.apply(l, r, x);}else {cout << t.prod(l, r).x2 << '\n';}}return 0;}