結果
問題 | No.1099 Range Square Sum |
ユーザー |
![]() |
提出日時 | 2020-06-27 05:41:39 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 478 ms / 2,000 ms |
コード長 | 3,044 bytes |
コンパイル時間 | 1,533 ms |
コンパイル使用メモリ | 141,472 KB |
最終ジャッジ日時 | 2025-01-11 12:34:28 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 30 |
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #include <time.h> #include <stack> #include <array> #include <list> #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair<ll, ll> P; template<typename Monoid, typename OperatorMonoid=Monoid> struct LazySegmentTree{ using F=function<Monoid(Monoid, Monoid)>; using G=function<Monoid(Monoid, OperatorMonoid, int)>; using H=function<OperatorMonoid(OperatorMonoid, OperatorMonoid)>; int sz; vector<Monoid> data; vector<OperatorMonoid> lazy; const F f; const G g; const H h; const Monoid e1; const OperatorMonoid e0; LazySegmentTree(int n, const F f, const G g, const H h, const Monoid &e1, const OperatorMonoid &e0): f(f), g(g), h(h), e1(e1), e0(e0){ sz=1; while(sz<n) sz<<=1; data.resize(2*sz-1, e1); lazy.resize(2*sz-1, e0); } void build(vector<Monoid> v){ for(int i=0; i<v.size(); i++) data[i+sz-1]=v[i]; for(int i=sz-2; i>=0; i--) data[i]=f(data[2*i+1], data[2*i+2]); } void eval(int k, int l, int r){ if(lazy[k]!=e0){ data[k]=g(data[k], lazy[k], r-l); if(k<sz-1){ lazy[2*k+1]=h(lazy[2*k+1], lazy[k]); lazy[2*k+2]=h(lazy[2*k+2], lazy[k]); } } lazy[k]=e0; } void update(int a, int b, const OperatorMonoid &x, int k, int l, int r){ eval(k, l, r); if(r<=a || b<=l) return; if(a<=l && r<=b){ lazy[k]=h(lazy[k], x); eval(k, l, r); }else{ update(a, b, x, 2*k+1, l, (l+r)/2); update(a, b, x, 2*k+2, (l+r)/2, r); data[k]=f(data[2*k+1], data[2*k+2]); } } void update(int a, int b, const OperatorMonoid &x){ return update(a, b, x, 0, 0, sz); } Monoid find(int a, int b, int k, int l, int r){ eval(k, l, r); if(b<=l || r<=a) return e1; if(a<=l && r<=b) return data[k]; else return f(find(a, b, 2*k+1, l, (l+r)/2), find(a, b, 2*k+2, (l+r)/2, r)); } Monoid find(int a, int b){ return find(a, b, 0, 0, sz); } Monoid operator[](const int &k){ return find(k, k+1); } }; int main() { int n; cin>>n; vector<P> a(n); for(int i=0; i<n; i++){ cin>>a[i].first; a[i].second=a[i].first*a[i].first; } auto f=[](P a, P b){ return P(a.first+b.first, a.second+b.second);}; auto g=[](P a, ll x, int len){ return P(a.first+x*len, a.second+2*x*a.first+x*x*len);}; auto h=[](ll x, ll y){ return x+y;}; LazySegmentTree<P, ll> seg(n, f, g, h, P(0, 0), 0); seg.build(a); int q; cin>>q; while(q--){ int t; cin>>t; if(t==1){ int l, r; ll x; cin>>l>>r>>x; l--; seg.update(l, r, x); }else{ int l, r; cin>>l>>r; l--; printf("%lld\n", seg.find(l, r).second); } } return 0; }