結果
問題 | No.1099 Range Square Sum |
ユーザー |
![]() |
提出日時 | 2020-06-27 14:34:37 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 725 ms / 2,000 ms |
コード長 | 3,740 bytes |
コンパイル時間 | 3,404 ms |
コンパイル使用メモリ | 206,812 KB |
最終ジャッジ日時 | 2025-01-11 12:51:27 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 30 |
ソースコード
#include "bits/stdc++.h"using namespace std;#define int long long#define REP(i, n) for (int i = 0; i < (int)n; ++i)#define RREP(i, n) for (int i = (int)n - 1; i >= 0; --i)#define FOR(i, s, n) for (int i = s; i < (int)n; ++i)#define RFOR(i, s, n) for (int i = (int)n - 1; i >= s; --i)#define ALL(a) a.begin(), a.end()#define IN(a, x, b) (a <= x && x < b)template<class T>inline void out(T t){cout << t << "\n";}template<class T,class... Ts>inline void out(T t,Ts... ts){cout << t << " ";out(ts...);}template<class T>inline bool CHMIN(T&a,T b){if(a > b){a = b;return true;}return false;}template<class T>inline bool CHMAX(T&a,T b){if(a < b){a = b;return true;}return false;}constexpr int INF = 1e18;template <typename T,typename E, typename F, typename G, typename H>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);}};//SegmentTree<int, int, decltype(f), decltype(g), decltype(h)> seg(f,g,h,ti,ei);signed main(){int N;cin >> N;vector<int>a(N);REP(i,N){cin >> a[i];}using T = tuple<int,int,int>;using E = 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;};T ti = {0ll,0ll,0ll};E ei = 0ll;vector<T>v(N);REP(i, N){v[i] = T(a[i] * a[i], a[i], 1);}SegmentTree seg(f,g,h,ti,ei);seg.build(v);int Q;cin >> Q;vector<T>ans;while(Q--){int t;cin >> t;if(t == 1){int l, r, x;cin >> l >> r >> x;l--;r--;seg.update(l, r + 1, x);}else{int l, r;cin >> l >> r;l--;r--;ans.emplace_back(seg.query(l, r + 1));}}for(auto &[e, hoge, huga]:ans)cout << e << endl;}