結果
問題 | No.1099 Range Square Sum |
ユーザー |
![]() |
提出日時 | 2020-06-26 21:44:27 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 376 ms / 2,000 ms |
コード長 | 3,350 bytes |
コンパイル時間 | 4,798 ms |
コンパイル使用メモリ | 207,860 KB |
最終ジャッジ日時 | 2025-01-11 11:09:43 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>using namespace std;template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}using Int = long long;const char newl = '\n';template <typename T,typename E>struct SegmentTree{using F = function<T(T,T)>;using G = function<T(T,E)>;using H = function<E(E,E)>;Int n,height;F f;G g;H h;T ti;E ei;vector<T> dat;vector<E> laz;SegmentTree(F f,G g,H h,T ti,E ei):f(f),g(g),h(h),ti(ti),ei(ei){}void init(Int n_){n=1;height=0;while(n<n_) n<<=1,height++;dat.assign(2*n,ti);laz.assign(2*n,ei);}void build(const vector<T> &v){Int n_=v.size();init(n_);for(Int i=0;i<n_;i++) dat[n+i]=v[i];for(Int i=n-1;i;i--)dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);}inline T reflect(Int k){return laz[k]==ei?dat[k]:g(dat[k],laz[k]);}inline void propagate(Int k){if(laz[k]==ei) return;laz[(k<<1)|0]=h(laz[(k<<1)|0],laz[k]);laz[(k<<1)|1]=h(laz[(k<<1)|1],laz[k]);dat[k]=reflect(k);laz[k]=ei;}inline void thrust(Int k){for(Int i=height;i;i--) propagate(k>>i);}inline void recalc(Int k){while(k>>=1)dat[k]=f(reflect((k<<1)|0),reflect((k<<1)|1));}void update(Int a,Int b,E x){if(a>=b) return;thrust(a+=n);thrust(b+=n-1);for(Int l=a,r=b+1;l<r;l>>=1,r>>=1){if(l&1) laz[l]=h(laz[l],x),l++;if(r&1) --r,laz[r]=h(laz[r],x);}recalc(a);recalc(b);}void set_val(Int a,T x){thrust(a+=n);dat[a]=x;laz[a]=ei;recalc(a);}T query(Int a,Int b){if(a>=b) return ti;thrust(a+=n);thrust(b+=n-1);T vl=ti,vr=ti;for(Int l=a,r=b+1;l<r;l>>=1,r>>=1) {if(l&1) vl=f(vl,reflect(l++));if(r&1) vr=f(reflect(--r),vr);}return f(vl,vr);}template<typename C>Int find(Int st,C &check,T &acc,Int k,Int l,Int r){if(l+1==r){acc=f(acc,reflect(k));return check(acc)?k-n:-1;}propagate(k);Int m=(l+r)>>1;if(m<=st) return find(st,check,acc,(k<<1)|1,m,r);if(st<=l&&!check(f(acc,dat[k]))){acc=f(acc,dat[k]);return -1;}Int vl=find(st,check,acc,(k<<1)|0,l,m);if(~vl) return vl;return find(st,check,acc,(k<<1)|1,m,r);}template<typename C>Int find(Int st,C &check){T acc=ti;return find(st,check,acc,1,0,n);}};//INSERT ABOVE HEREsigned main(){cin.tie(0);ios::sync_with_stdio(0);using T = tuple<Int, Int, Int>;auto f=[](T a,T b){auto [ax,ay,az]=a;auto [bx,by,bz]=b;return T(ax+bx,ay+by,az+bz);};auto g=[](T a,Int b){auto [ax,ay,az]=a;return T(ax+2*ay*b+az*b*b,ay+az*b,az);};auto h=[](Int a,Int b){return a+b;};using E = Int;T ti(0,0,0);E ei(0);SegmentTree<T, E> seg(f,g,h,ti,ei);Int n;cin>>n;vector<Int> as(n);for(Int i=0;i<n;i++) cin>>as[i];vector<T> vt(n);for(Int i=0;i<n;i++) vt[i]=T(as[i]*as[i],as[i],1);seg.build(vt);Int q;cin>>q;for(Int i=0;i<q;i++){Int t;cin>>t;if(t==1){Int l,r,x;cin>>l>>r>>x;l--;seg.update(l,r,x);}if(t==2){Int l,r;cin>>l>>r;l--;cout<<get<0>(seg.query(l,r))<<newl;}}return 0;}