結果
問題 | No.1099 Range Square Sum |
ユーザー |
![]() |
提出日時 | 2020-05-17 21:12:23 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 186 ms / 2,000 ms |
コード長 | 1,895 bytes |
コンパイル時間 | 2,080 ms |
コンパイル使用メモリ | 175,688 KB |
実行使用メモリ | 16,512 KB |
最終ジャッジ日時 | 2024-11-22 16:37:58 |
合計ジャッジ時間 | 5,194 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 30 |
ソースコード
#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;}