結果
問題 | No.1099 Range Square Sum |
ユーザー |
👑 ![]() |
提出日時 | 2020-10-03 19:05:55 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 940 ms / 2,000 ms |
コード長 | 3,229 bytes |
コンパイル時間 | 1,747 ms |
コンパイル使用メモリ | 176,560 KB |
実行使用メモリ | 61,932 KB |
最終ジャッジ日時 | 2024-07-18 04:47:45 |
合計ジャッジ時間 | 12,299 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 30 |
ソースコード
#include<bits/stdc++.h>using namespace std;using LL = long long;using ULL = unsigned long long;#define rep(i,n) for(int i=0; i<(n); i++)template<class S,S(*op)(S a, S b),S(*e)(),class F,S(*mapping)(F a, S b),F(*composition)(F a, F b),F(*id)()>struct lazy_segtree {private:struct Node { S v; F r; };int N;vector<Node> V;void spread(int i) {V[i].v = mapping(V[i].r, V[i].v);if (i < N) {V[i * 2].r = composition(V[i].r, V[i * 2].r);V[i * 2 + 1].r = composition(V[i].r, V[i * 2 + 1].r);}V[i].r = id();}public:lazy_segtree(int n) {N = 1; while (N < n) N *= 2;V.assign(N * 2, { e(),id() });}lazy_segtree(vector<S> A) {N = 1; while (N < A.size()) N *= 2;V.assign(N * 2, { e(),id() });rep(i, A.size()) V[N + i].v = A[i];for (int i = N - 1; i >= 1; i--)V[i].v = op(V[i * 2].v, V[i * 2 + 1].v);}void set(int p, S v) {p += N;for (int d = N; d >= 1; d /= 2) spread(p / d);V[p].v = v;int z = 1;while (p != 1) {p /= 2; z *= 2;spread(p * 2); spread(p * 2 + 1);V[p].v = op(V[p * 2].v, V[p * 2 + 1].v);}}S get(int p) {p += N;for (int d = N; d >= 1; d /= 2) spread(p / d);return V[p].v;}void apply(int l, int r, F v, int a = 0, int b = 0, int i = -1) {if (i == -1) { a = 0; b = N; i = 1; }if (r <= a || b <= l) { spread(i); return; }else if (l <= a && b <= r) { V[i].r = composition(v, V[i].r); spread(i); return; }spread(i);apply(l, r, v, a, (a + b) / 2, i * 2);apply(l, r, v, (a + b) / 2, b, i * 2 + 1);V[i].v = op(V[i * 2].v, V[i * 2 + 1].v);}S prod(int l, int r, int a = 0, int b = 0, int i = -1) {if (i == -1) { a = 0; b = N; i = 1; }if (r <= a || b <= l) return e();spread(i);if (l <= a && b <= r) return V[i].v;S q1 = prod(l, r, a, (a + b) / 2, i * 2);S q2 = prod(l, r, (a + b) / 2, b, i * 2 + 1);q1 = op(q1, q2);return q1;}};struct S { LL m[3] = {}; };S op(S l, S r) { S res; rep(i, 3) res.m[i] = l.m[i] + r.m[i]; return res; }S e() { return { {0,0,0} }; }struct F { LL m[3][3] = {}; };S mapping(F f, S a) { S res; rep(i, 3) rep(j, 3) res.m[i] += a.m[j] * f.m[j][i]; return res; }F composition(F f, F g) { F res; rep(i, 3) rep(j, 3) rep(k, 3) res.m[i][j] += g.m[i][k] * f.m[k][j]; return res; }F id() { return { {{1,0,0},{0,1,0},{0,0,1}} }; }using RQ = lazy_segtree<S, op, e, F, mapping, composition, id>;int main() {int N; cin >> N;vector<S> rqinit(N);rep(i, N) { LL a; cin >> a; rqinit[i] = S{ {a * a,a,1} }; }RQ G(rqinit);int Q; cin >> Q;rep(i, Q) {int c; cin >> c;if (c == 1) {int l, r; LL x; cin >> l >> r >> x; l--;G.apply(l, r, F{ {{1,0,0},{2 * x,1,0},{x*x,x,1}} });}else if (c == 2) {int l, r; cin >> l >> r; l--;cout << G.prod(l, r).m[0] << endl;}}return 0;}