結果
問題 | No.1099 Range Square Sum |
ユーザー |
![]() |
提出日時 | 2020-06-26 22:25:59 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 224 ms / 2,000 ms |
コード長 | 3,221 bytes |
コンパイル時間 | 1,246 ms |
コンパイル使用メモリ | 104,824 KB |
実行使用メモリ | 20,228 KB |
最終ジャッジ日時 | 2024-07-04 22:09:17 |
合計ジャッジ時間 | 4,867 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 30 |
ソースコード
#include <iostream>#include <algorithm>#include <string>#include <vector>#include <cmath>#include <map>#include <queue>#include <iomanip>#include <set>#include <tuple>#define mkp make_pair#define mkt make_tuple#define rep(i,n) for(int i = 0; i < (n); ++i)#define all(v) v.begin(),v.end()using namespace std;typedef long long ll;const ll MOD=1e9+7;template<class T> void chmin(T &a,const T &b){if(a>b) a=b;}template<class T> void chmax(T &a,const T &b){if(a<b) a=b;}#include <functional>template< typename T, typename S >struct LazySegmentTree{int n;vector<T> data;vector<S> lazy;T te;S se;inline void merge_functions(S& lazy,S& val){lazy+=val;//lazy=val;}inline void operate(T& data,S& val,int len){//data+=val*len;//data=val*len;//data+=val;//data=val;T tmp;tmp.first=data.first+val*len;tmp.second=data.second+(val*val)*len+2*val*data.first;data=tmp;}inline T merge_values(T& x,T& y){return mkp(x.first+y.first,x.second+y.second);//return min(x,y);//return max(x,y);}LazySegmentTree(){}LazySegmentTree(int sz,T te,S se):te(te),se(se){n=1;while(n<sz) n*=2;data.resize(2*n-1,te);lazy.resize(2*n-1,se);}void build(vector<T> &A){for(int k=0;k<int(A.size());k++) data[k+n-1]=A[k];for(int k=n-2;k>=0;k--) data[k]=merge_values(data[2*k+1],data[2*k+2]);}void eval(int k,int l,int r){if(lazy[k]==se) return;operate(data[k],lazy[k],r-l);if(r-l>1){merge_functions(lazy[2*k+1],lazy[k]);merge_functions(lazy[2*k+2],lazy[k]);}lazy[k]=se;}void update(int a,int b,S val,int k=0,int l=0,int r=-1){if(r<0) r=n;eval(k,l,r);if(b<=l||r<=a) return;if(a<=l&&r<=b){merge_functions(lazy[k],val);eval(k,l,r);}else{update(a,b,val,2*k+1,l,(l+r)/2);update(a,b,val,2*k+2,(l+r)/2,r);data[k]=merge_values(data[2*k+1],data[2*k+2]);}}T query(int a,int b,int k=0,int l=0,int r=-1){if(r<0) r=n;eval(k,l,r);if(b<=l||r<=a) return te;if(a<=l&&r<=b) return data[k];T vl=query(a,b,2*k+1,l,(l+r)/2);T vr=query(a,b,2*k+2,(l+r)/2,r);return merge_values(vl,vr);}};/*LazySegmentTree<ll,ll> seg(N,te,se);vector<ll> init(N,0);seg.build(init);*/const pair<ll,ll> TE=mkp(0,0);const ll SE=0;int main(){cin.tie(0);ios::sync_with_stdio(false);int N;cin>>N;vector<ll> A(N);rep(i,N) cin>>A[i];LazySegmentTree<pair<ll,ll>,ll> seg(N,TE,SE);vector<pair<ll,ll>> init(N,mkp(0,0));rep(i,N) init[i]=mkp(A[i],A[i]*A[i]);seg.build(init);int Q;cin>>Q;rep(i,Q){int t;cin>>t;if(t==1){int l,r;ll x;cin>>l>>r>>x;l--;r--;seg.update(l,r+1,x);}else{int l,r;cin>>l>>r;l--;r--;cout<<seg.query(l,r+1).second<<"\n";}}return 0;}