結果

問題 No.1099 Range Square Sum
ユーザー plz_mymelody
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

// 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0