結果
問題 | No.1099 Range Square Sum |
ユーザー |
![]() |
提出日時 | 2020-06-26 22:00:51 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 147 ms / 2,000 ms |
コード長 | 3,216 bytes |
コンパイル時間 | 2,252 ms |
コンパイル使用メモリ | 200,100 KB |
最終ジャッジ日時 | 2025-01-11 11:27:38 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;template <class T, class U> using Pa = pair<T, U>;template <class T> using vec = vector<T>;template <class T> using vvec = vector<vec<T>>;template<typename Monoid,typename OperatorMonoid,typename F,typename G,typename H>class LazySegmentTree {private:int sz,height;vec<Monoid> data;vec<OperatorMonoid> lazy;const F op;const G homo;const H comp;const Monoid e;const OperatorMonoid Oe;public:LazySegmentTree(int n,const F op,const G homo,const H comp,const Monoid &e,const OperatorMonoid Oe): op(op),homo(homo),comp(comp),e(e),Oe(Oe) {sz = 1;height = 0;while(sz<=n) sz <<= 1,height++;data.assign(2*sz,e);lazy.assign(2*sz,Oe);}void set(int k,const Monoid &x) {data[k+sz] = x;}void build() {for(int k=sz-1;k>0;k--) {data[k] = op(data[2*k], data[2*k+1]);}}inline void propagate(int k) {if(lazy[k]!=Oe) {lazy[2*k] = comp(lazy[2*k], lazy[k]);lazy[2*k+1] = comp(lazy[2*k+1], lazy[k]);data[k] = reflect(k);lazy[k] = Oe;}}inline Monoid reflect(int k) {return lazy[k] == Oe? data[k]:homo(data[k],lazy[k]);}inline void recalc(int k) {while(k>>=1) data[k] = op(reflect(2*k), reflect(2*k+1));}inline void thrust(int k) {for(int i=height;i>0;i--) propagate(k>>i);}void update(int a, int b, const OperatorMonoid &x) {thrust(a+=sz);thrust(b+=sz-1);for(int l=a,r=b+1;l<r;l>>=1,r>>=1) {if(l&1) lazy[l] = comp(lazy[l],x),++l;if(r&1) --r, lazy[r] = comp(lazy[r],x);}recalc(a);recalc(b);}Monoid query(int a, int b) {thrust(a+=sz);thrust(b+=sz-1);Monoid L = e, R = e;for(int l=a, r=b+1;l<r;l>>= 1,r>>=1) {if(l&1) L = op(L,reflect(l++));if(r&1) R = op(reflect(--r),R);}return op(L,R);}Monoid operator[](const int &k) {return query(k,k+1);}};int main(){cin.tie(0);ios::sync_with_stdio(false);struct state{ll sum,sum2,len;};auto op = [](state L,state R)->state{ll sum = L.sum+R.sum;ll sum2 = L.sum2+R.sum2;ll len = L.len+R.len;return {sum,sum2,len};};auto func = [](state S,ll x)->state{ll sum = S.sum+x*S.len;ll sum2 = S.sum2+2*S.sum*x+x*x*S.len;return {sum,sum2,S.len};};auto comp = [](ll x,ll y){return x+y;};int N;cin >> N;state e = {0,0,0};LazySegmentTree seg(N,op,func,comp,e,0);for(int i=0;i<N;i++){ll a;cin >> a;seg.set(i,(state){a,a*a,1});}seg.build();int Q;cin >> Q;while(Q--){int t,l,r;cin >> t >> l >> r;l--,r--;if(t==1){ll x;cin >> x;seg.update(l,r+1,x);}else{cout << seg.query(l,r+1).sum2 << "\n";}}}