結果
問題 | No.1099 Range Square Sum |
ユーザー | QCFium |
提出日時 | 2020-05-17 21:12:23 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 207 ms / 2,000 ms |
コード長 | 1,895 bytes |
コンパイル時間 | 2,019 ms |
コンパイル使用メモリ | 175,416 KB |
実行使用メモリ | 16,512 KB |
最終ジャッジ日時 | 2024-05-02 05:32:54 |
合計ジャッジ時間 | 5,302 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 3 ms
5,376 KB |
testcase_12 | AC | 3 ms
5,376 KB |
testcase_13 | AC | 3 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
testcase_15 | AC | 2 ms
5,376 KB |
testcase_16 | AC | 3 ms
5,376 KB |
testcase_17 | AC | 3 ms
5,376 KB |
testcase_18 | AC | 3 ms
5,376 KB |
testcase_19 | AC | 3 ms
5,376 KB |
testcase_20 | AC | 3 ms
5,376 KB |
testcase_21 | AC | 196 ms
16,384 KB |
testcase_22 | AC | 195 ms
16,384 KB |
testcase_23 | AC | 195 ms
16,412 KB |
testcase_24 | AC | 202 ms
16,384 KB |
testcase_25 | AC | 207 ms
16,384 KB |
testcase_26 | AC | 150 ms
16,384 KB |
testcase_27 | AC | 147 ms
16,384 KB |
testcase_28 | AC | 151 ms
16,488 KB |
testcase_29 | AC | 152 ms
16,512 KB |
testcase_30 | AC | 147 ms
16,384 KB |
ソースコード
#include <bits/stdc++.h> int ri() { int n; scanf("%d", &n); return n; } struct SegTree { int n; std::vector<int64_t> sum; std::vector<int64_t> ssum; std::vector<int> size; std::vector<int> added; SegTree (const std::vector<int> &a) { for (n = 1; n < (int) a.size(); n <<= 1); sum.resize(n << 1); ssum.resize(n << 1); added.resize(n << 1); size.resize(n << 1); for (int i = 0; i < (int) a.size(); i++) { sum[i + n] = a[i]; ssum[i + n] = (int64_t) a[i] * a[i]; size[i + n] = 1; } for (int i = n; --i; ) fetch(i), size[i] = size[i << 1] << 1; } void flush(int i) { if (added[i]) { ssum[i] += (int64_t) size[i] * added[i] * added[i] + (int64_t) sum[i] * added[i] * 2; sum[i] += (int64_t) size[i] * added[i]; if (i < n) { added[i << 1] += added[i]; added[i << 1 | 1] += added[i]; } added[i] = 0; } } void fetch(int i) { sum[i] = sum[i << 1] + sum[i << 1 | 1]; ssum[i] = ssum[i << 1] + ssum[i << 1 | 1]; } template<class T> void dive(int l, int r, int node, int node_l, int node_r, const T &func) { flush(node); if (r <= node_l || l >= node_r) return; if (l <= node_l && r >= node_r) func(node); else { int mid = node_l + ((node_r - node_l) >> 1); dive(l, r, node << 1, node_l, mid, func); dive(l, r, node << 1 | 1, mid, node_r, func); fetch(node); } } void add(int l, int r, int val) { dive(l, r, 1, 0, n, [&] (int node) { added[node] += val; flush(node); }); } int64_t get_ssum(int l, int r) { int64_t res = 0; dive(l, r, 1, 0, n, [&] (int node) { res += ssum[node]; }); return res; } }; int main() { int n = ri(); std::vector<int> a(n); for (auto &i : a) i = ri(); SegTree tree(a); int q = ri(); for (int i = 0; i < q; i++) { int t = ri(); int l = ri() - 1; int r = ri(); if (t == 1) tree.add(l, r, ri()); else printf("%" PRId64 "\n", tree.get_ssum(l, r)); } return 0; }