結果
問題 | No.1099 Range Square Sum |
ユーザー |
|
提出日時 | 2020-06-28 22:17:07 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 289 ms / 2,000 ms |
コード長 | 3,726 bytes |
コンパイル時間 | 1,537 ms |
コンパイル使用メモリ | 177,556 KB |
実行使用メモリ | 18,704 KB |
最終ジャッジ日時 | 2024-07-08 08:34:50 |
合計ジャッジ時間 | 7,195 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef pair<int,int> P;typedef long long ll;typedef long double ld;const int inf=1e9+7;const ll longinf=1LL<<60;#define REP(i,m,n) for(ll i=(int)(m) ; i < (int) (n) ; ++i )#define rep(i,n) REP(i,0,n)#define F first#define S secondconstexpr char ln = '\n';const int mx=200010;const ll mod=1e9+7;template<typename F, typename T, typename Func_mf, typename Func_op, typename Func_mv>struct LazySegtree { //imos でもいけませんか???ll n, n_org;vector<T> dat;vector<F> laz;Func_mf merge_functions; //lazyとlazyの演算Func_op operate; //dataとlazyの演算Func_mv merge_values; //dataとdataの演算F fe; //lazyの単位元かつ初期値T te; //dataの単位元かつ初期値LazySegtree(){}LazySegtree(ll 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.resize(2*n-1, te);laz.resize(2*n-1, fe);}void build(vector<T>& A){for(ll k=0; k<ll(A.size()); k++) dat[k+n-1] = A[k];for(ll k=n-2; k>=0; k--) dat[k] = merge_values(dat[2*k+1], dat[2*k+2]);}void update(ll a, ll b, F x){ //[a,b)をupdate b]:b+1update(a, b, x, 0, 0, n);}T get(ll a, ll b){ //[a,b)から(最小値とか和とかを)get b]:b+1return query(a, b, 0, 0, n);}private:void eval(ll k, ll 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;}T query(ll a, ll b, ll k, ll lb, ll rb){eval(k, rb-lb);if(rb<=a || b<=lb) return te;if(a<=lb && rb<=b) return dat[k];ll 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);}void update(ll a, ll b, F x, ll k, ll lb, ll 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{ll 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]);}}};auto make_segtree = [](ll N){ //auto make_segtree = [&](ll N)using F = ll;using T = pair<ll,ll>;auto merge_functions = [](F& f, F& g){f += g;};auto operate = [](T& v, F& f, ll w){v.F += 2*v.S*f + w*f*f; v.S += w*f;};auto merge_values = [](T& a, T& b){return pair<ll,ll>(a.F+b.F, a.S+b.S);};F fe = 0;T te = pair<ll,ll>(0,0);return LazySegtree<F, T, decltype(merge_functions), decltype(operate), decltype(merge_values)>(N, merge_functions, operate, merge_values, fe, te);};/*auto st = make_segtree(n);vector<ll> init(n);st.build(init);*/int main(){ll n;cin >> n;vector<pair<ll,ll>> a(n);rep(i,n){cin >> a[i].S;a[i].F = a[i].S*a[i].S;}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(l-1,r,x);} else {int l,r; cin >> l >> r;ll ans = st.get(l-1,r).F;cout << ans << ln;}}return 0;}