結果
問題 | No.1099 Range Square Sum |
ユーザー |
|
提出日時 | 2020-06-27 22:48:52 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 243 ms / 2,000 ms |
コード長 | 3,715 bytes |
コンパイル時間 | 1,960 ms |
コンパイル使用メモリ | 201,384 KB |
最終ジャッジ日時 | 2025-01-11 13:05:03 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>using namespace std;template<class Monoid, class OperatorMonoid, class FunctionM, class FunctionMO, class FunctionO>struct LazySegmentTree {int N; vector<Monoid> segment; vector<OperatorMonoid> lazy;const FunctionM FuncM; const FunctionMO FuncMO; const FunctionO FuncO;const Monoid idM; const OperatorMonoid idOM;LazySegmentTree(int n, const FunctionM FuncM, const FunctionMO FuncMO, const FunctionO FuncO,const Monoid idM, const OperatorMonoid idOM): FuncM(FuncM), FuncMO(FuncMO), FuncO(FuncO), idM(idM), idOM(idOM) {N = 1;while (N < n) N <<= 1;segment.assign(2 * N, idM); lazy.assign(2 * N, idOM);}LazySegmentTree(int n, const FunctionM FuncM, const FunctionMO FuncMO, const FunctionO FuncO,const Monoid idM, const OperatorMonoid idOM, const Monoid initVal): FuncM(FuncM), FuncMO(FuncMO), FuncO(FuncO), idM(idM), idOM(idOM) {N = 1;while (N < n) N <<= 1;segment.assign(2 * N, initVal); lazy.assign(2 * N, idOM);}void set(int num, Monoid x) {segment[N + num] = x;}void build() {for (int k = N - 1; k > 0; k--) {segment[k] = FuncM(segment[2*k], segment[2*k+1]);}}void propagate(int k, int len){if (lazy[k] != idOM) {if (k < N) {lazy[2*k] = FuncO(lazy[2*k], lazy[k]);lazy[2*k+1] = FuncO(lazy[2*k+1], lazy[k]);}segment[k] = FuncMO(segment[k], lazy[k], len);lazy[k] = idOM;}}// update:[a, b)Monoid update(int a, int b, const OperatorMonoid x) {return update(a, b, x, 1, 0, N);}Monoid update(int a, int b, const OperatorMonoid x, int k, int l, int r){propagate(k, r-l);if (b <= l || r <= a) {return segment[k];} else if (a <= l && r <= b) {lazy[k] = FuncO(lazy[k], x);propagate(k, r-l);return segment[k];} else {int m = (l + r) / 2;return segment[k] = FuncM(update(a, b, x, 2*k, l, m), update(a, b, x, 2*k+1, m, r));}}// query:[a, b)Monoid query(int a, int b) {return query(a, b, 1, 0, N);}Monoid query(int a, int b, int k, int l, int r) {propagate(k, r-l);if (b <= l || r <= a) {return idM;} else if (a <= l && r <= b) {return segment[k];} else {int m = (l + r) / 2;return FuncM(query(a, b, 2*k, l, m), query(a, b, 2*k+1, m, r));}}// 0-indexed numbering;Monoid operator[](const int &k) {return query(k, k + 1);}};using D = pair<long long, long long>;auto F = [](D a, D b) -> D {return {a.first + b.first, a.second + b.second};};auto G = [](D a, long long b, int len) -> D {long long y = a.second + b * len;long long x = b * b * len + 2 * b * a.second + a.first;return {x, y};};auto H = [](long long a, long long b) {return a + b;};int main() {cin.tie(nullptr);ios::sync_with_stdio(false);int N; cin >> N;LazySegmentTree lst(N, F, G, H, D(0, 0), 0);for (int i = 0; i < N; i++) {long long A; cin >> A;lst.update(i, i+1, A);}int Q; cin >> Q;for (int i = 0; i < Q; i++) {int type; cin >> type;if (type == 1) {int l, r; long long x;cin >> l >> r >> x;lst.update(--l, r, x);} else {int l, r; cin >> l >> r;auto ret = lst.query(--l, r);cout << ret.first << "\n";}}return 0;}