結果
問題 | No.1099 Range Square Sum |
ユーザー |
![]() |
提出日時 | 2020-06-27 01:29:07 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 321 ms / 2,000 ms |
コード長 | 9,657 bytes |
コンパイル時間 | 1,909 ms |
コンパイル使用メモリ | 180,736 KB |
実行使用メモリ | 18,628 KB |
最終ジャッジ日時 | 2024-07-05 04:59:46 |
合計ジャッジ時間 | 6,400 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 30 |
ソースコード
// warm heart, wagging tail,and a smile just for you!// ███████████// ███╬╬╬╬╬╬╬╬╬╬███// ███╬╬╬╬╬████╬╬╬╬╬╬███// ███████████ ██╬╬╬╬╬████╬╬████╬╬╬╬╬██// █████████╬╬╬╬╬████████████╬╬╬╬╬██╬╬╬╬╬╬███╬╬╬╬╬██// ████████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████████╬╬╬╬╬╬██╬╬╬╬╬╬╬██// ████╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████████╬╬╬╬╬╬╬╬╬╬╬██// ███╬╬╬█╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬███╬╬╬╬╬╬╬█████// ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬████████╬╬╬╬╬██// ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬███╬╬╬╬╬╬╬╬╬███// ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████╬╬╬╬╬╬╬██// ████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬████╬╬╬╬╬████// █████████████╬╬╬╬╬╬╬╬██╬╬╬╬╬████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬███╬╬╬╬██████// ████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬██████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██████╬╬╬╬╬╬╬███████████╬╬╬╬╬╬╬╬██╬╬╬██╬╬╬██// ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬████╬╬╬╬╬╬╬╬╬╬╬█╬╬╬╬╬╬╬██╬╬╬╬╬╬╬╬██// ██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬▓▓▓▓▓▓╬╬╬████╬╬████╬╬╬╬╬╬╬▓▓▓▓▓▓▓▓██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬╬╬╬███// ██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██████▓▓▓▓▓▓▓╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬▓▓▓▓▓▓▓██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬█████// ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬███╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬████████// ███╬╬╬╬╬╬╬╬╬╬╬╬╬█████╬╬╬╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬███╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██// ██████████████ ████╬╬╬╬╬╬███████████████████████████╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬████// ███████ █████ ███████████████████//#include "bits/stdc++.h"using namespace std;#define INF (1<<30)#define LINF (1LL<<60)#define fs first#define sc second#define int long long#define FOR(i,a,b) for(int i=(a);i<(b);++i)#define RFOR(i,a,b) for(int i = (b-1);i>=(a);--i)#define REP(i,n) FOR(i,0,(n))#define RREP(i,n) RFOR(i,0,(n))#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)#define range(i,a,b) ((a)<=(i) && (i)<(b))#define debug(x) cout << #x << " = " << (x) << endl#define SP << " " <<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;}#define MSB(x) (63-__builtin_clzll(x))#define pcnt(x) (__builtin_popcountll(x))#define parity(i,j) (i&(1LL<<j))typedef pair<int,int> P;typedef tuple<int,int,int> T;typedef vector<int> vec;typedef vector<vector<int>> mat;// //高速化// 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)>;// ~~~// };// SegmentTree<int, int, decltype(f), decltype(g), decltype(h)> seg(f,g,h,ti,ei);template <typename T,typename E>struct SegmentTree{using F = function<T(T,T)>;using G = function<T(T,E,int)>;using H = function<E(E,E)>;int n;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;while(n<n_) n<<=1;dat.assign((n<<1)-1,ti);laz.assign((n<<1)-1,ei);}void build(const vector<T> &v){int n_=v.size();init(n_);for(int i=0;i<n_;i++) dat[n+i-1]=v[i];for(int i=n-2;i>=0;i--)dat[i]=f(dat[(i<<1)+2],dat[(i<<1)|1]);}void eval(int k,int l,int r){if(laz[k]==ei)return;dat[k] = g(dat[k], laz[k], r-l);if(r-l>1){laz[(k<<1)|1] = h(laz[(k<<1)|1], laz[k]);laz[(k<<1)+2] = h(laz[(k<<1)+2], laz[k]);}laz[k]=ei;}void update(int a, int b, E x,int k=0,int l=0,int r=-1){if(r<0)r=n;eval(k,l,r);if(r<=a||b<=l)return;if(a<=l&&r<=b){laz[k] = h(laz[k], x);eval(k,l,r);}else {update(a,b,x,(k<<1)|1,l,(l+r)/2);update(a,b,x,(k<<1)+2,(l+r)/2,r);dat[k]=f(dat[(k<<1)|1], dat[(k<<1)+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(r<=a||b<=l)return ti;if(a<=l&&r<=b)return dat[k];T xl=query(a,b,(k<<1)|1,l,(l+r)/2);T xr=query(a,b,(k<<1)+2,(l+r)/2,r);return f(xl, xr);}//lower_find(l,r,fanc): fancを満たす区間[0,id)なるidの最小値を返す. ng < okのときtemplate<typename C>int lower_find(int a, int b, C &check, T x, int k=1, int l=0, int r=-1){if(r<0)r=n;if(!check(f(x,dat[k]))||r<=a||b<=l)return -1;if(r-l==1)return l;int xl = lower_find(a,b,check,x,(k<<1),l,(l+r)/2);if(xl>=0)return xl;x = f(x,dat[(k<<1)]);return lower_find(a,b,check,x,(k<<1)|1,(l+r)/2,r);}template<typename C>int lower_find(int a, int b, C &check){T x=ti;return lower_find(a,b,check,x);}//upper_find(l,r,fanc): fancを満たす区間[0,id)なるidの最小値を返す. ok < ngのときtemplate<typename C>int upper_find(int a, int b, C &check, T x, int k=2, int l=0, int r=-1){if(r<0)r=n;if(r<=a||b<=l)return -1;if(r-l==1)return l;if(check(f(x,dat[k]))){int xr = upper_find(a,b,check,f(x,dat[k]),((k+1)<<1),(l+r)/2,r);if(xr>=0)return xr;}return upper_find(a,b,check,x,(k<<1),l,(l+r)/2);}template<typename C>int upper_find(int a, int b, C &check){T x=ti;return upper_find(a,b,check,x);}};//ex) RAQ & RSQ//auto f = [](int a, int b){return a+b;};//auto g = [](int a, int b, int len){return a+b*len;};//auto h = [](int a, int b){return a+b;};//ex) RAQ & RMQ//auto f = [](int a, int b){return min(a,b);};//auto g = [](int a, int b, int len){return a+b;};//auto h = [](int a, int b){return a+b;};signed main(){ios::sync_with_stdio(false);cin.tie(0);int n;cin >> n;vector<P> a(n);REP(i,n) cin >> a[i].sc, a[i].fs = a[i].sc*a[i].sc;auto f = [](P a, P b){return P(a.fs+b.fs,a.sc+b.sc);};auto g = [](P a, int b, int len){return P(a.fs+2*a.sc*b+len*b*b,a.sc+len*b);};auto h = [](int a, int b){return a+b;};SegmentTree<P,int> seg(f,g,h,P(0,0),0);seg.build(a);int q;cin >> q;REP(_,q){int x;cin >> x;if(x==1){int l,r,z;cin >> l >> r >> z;seg.update(l-1,r,z);}else{int l,r;cin >> l >> r;cout << seg.query(l-1,r).fs << endl;}}return 0;}