結果
問題 | No.1099 Range Square Sum |
ユーザー |
|
提出日時 | 2020-06-26 21:54:43 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 366 ms / 2,000 ms |
コード長 | 4,418 bytes |
コンパイル時間 | 1,995 ms |
コンパイル使用メモリ | 202,908 KB |
最終ジャッジ日時 | 2025-01-11 11:21:45 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>using namespace std;template<typename F, typename T, typename Func_mf, typename Func_op, typename Func_mv>struct LazySegtree {int n, n_org;vector<T> dat;vector<F> laz;Func_mf merge_functions;Func_op operate;Func_mv merge_values;F fe;T te;LazySegtree(){}LazySegtree(int n_org,Func_mf merge_functions,Func_op operate,Func_mv merge_values,F fe, T te):n_org(n_org),merge_functions(merge_functions),operate(operate),merge_values(merge_values),fe(fe), te(te){n = 1;while(n < n_org) n <<= 1;dat.assign(2*n-1, te);laz.assign(2*n-1, fe);}void build(vector<T>& A){for(int k=0; k<int(A.size()); k++) dat[k+n-1] = A[k];for(int k=n-2; k>=0; k--) dat[k] = merge_values(dat[2*k+1], dat[2*k+2]);}void eval(int k, int w){if(laz[k] == fe) return;operate(dat[k], laz[k], w);if(k < n-1){merge_functions(laz[2*k+1], laz[k]);merge_functions(laz[2*k+2], laz[k]);}laz[k] = fe;}void update_between(int a, int b, F x){update(a, b+1, x, 0, 0, n);}void update(int a, int b, F x, int k, int lb, int rb){eval(k, rb-lb);if(b <= lb || rb <= a) return;if(a <= lb && rb <= b){merge_functions(laz[k], x);eval(k, rb-lb);}else{int mb = (lb+rb)>>1;update(a, b, x, 2*k+1, lb, mb);update(a, b, x, 2*k+2, mb, rb);dat[k] = merge_values(dat[2*k+1], dat[2*k+2]);}}T get_between(int a, int b){return query(a, b+1, 0, 0, n);}T query(int a, int b, int k, int lb, int rb){eval(k, rb-lb);if(rb<=a || b<=lb) return te;if(a<=lb && rb<=b) return dat[k];int mb = (lb+rb)>>1;T vl = query(a, b, 2*k+1, lb, mb);T vr = query(a, b, 2*k+2, mb, rb);return merge_values(vl, vr);}// [S, t] が条件checkを満たす最大のtを求めるtemplate<typename Func_ck>int lower_bound(int S, Func_ck check){T val = get_between(S, S);int k = S+n-1;int lb = S, rb = S+1;while(true){while(k%2){k = (k-1)/2;rb += rb-lb;}int w = rb-lb;eval(k, w);T val2 = merge_values(val, dat[k]);if(check(val2)){if(rb == n) return n_org-1;val = val2;k++;lb += w;rb += w;}else{break;}}while(k<n-1){int wh = (rb-lb)>>1;eval(2*k+1, wh);eval(2*k+2, wh);T val2 = merge_values(val, dat[2*k+1]);if(check(val2)){val = val2;k = 2*k+2;lb += wh;}else{k = 2*k+1;rb -= wh;}}return min(lb, n_org)-1;}};auto make_segtree = [](int N){using F = int64_t;// 2乗和、1乗和using T = pair<int64_t, int64_t>;auto merge_functions = [](F& f, F& g){f += g;};auto operate = [](T& v, F& f, int w){v.first += 2*v.second*f + w*f*f;v.second += w*f;};auto merge_values = [](T& a, T& b){return make_pair(a.first+b.first, a.second+b.second);};F fe = 0;T te = {0, 0};return LazySegtree<F, T, decltype(merge_functions), decltype(operate), decltype(merge_values)>(N, merge_functions, operate, merge_values, fe, te);};int main(){int N;cin >> N;vector<pair<int64_t, int64_t>> A(N);for(int i=0; i<N; i++){int64_t a;cin >> a;A[i] = {a*a, a};}auto st = make_segtree(N);st.build(A);int Q;cin >> Q;while(Q--){int t;cin >> t;if(t == 1){int l, r, x;cin >> l >> r >> x;st.update_between(l-1, r-1, x);}else{int l, r;cin >> l >> r;int64_t ans = st.get_between(l-1, r-1).first;cout << ans << endl;}}return 0;}