結果
問題 | No.1099 Range Square Sum |
ユーザー |
![]() |
提出日時 | 2020-07-17 16:26:33 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 523 ms / 2,000 ms |
コード長 | 4,367 bytes |
コンパイル時間 | 3,419 ms |
コンパイル使用メモリ | 210,608 KB |
最終ジャッジ日時 | 2025-01-11 21:47:43 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h> using namespace std; inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;} template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();} typedef long long ll; typedef vector<int> VI; typedef vector<VI> VVI; typedef vector<long long> VL; typedef vector<vector<long long>> VVL; typedef vector<string> VS; typedef pair<ll,ll> P; typedef tuple<int,int,int> tpl; #define ALL(a) (a).begin(),(a).end() #define SORT(c) sort((c).begin(),(c).end()) #define REVERSE(c) reverse((c).begin(),(c).end()) #define EXIST(m,v) (m).find((v)) != (m).end() #define LB(a,x) lower_bound((a).begin(), (a).end(), x) - (a).begin() #define UB(a,x) upper_bound((a).begin(), (a).end(), x) - (a).begin() #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) #define RFOR(i,a,b) for(int i=(a)-1;i>=(b);--i) #define RREP(i,n) RFOR(i,n,0) #define en "\n" constexpr double EPS = 1e-9; constexpr double PI = 3.1415926535897932; constexpr int INF = 2147483647; constexpr long long LINF = 1LL<<60; constexpr long long MOD = 1000000007; // 998244353; #define dump(x) cerr << #x << " = " << (x) << endl; #define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl; template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } template <typename T,typename E> struct LazySegmentTree{ typedef function<T(T,T)> F; typedef function<T(T,T)> G; typedef function<E(E,E)> H; typedef function<T(E,ll)> P; int n; F f; G g; H h; P p; T d1; E d0; vector<T> val; vector<E> lazy; LazySegmentTree(vector<T> a, F f_, G g_, H h_, T d1_, E d0_, P p_=[](E a,ll b){return a;}): f(f_),g(g_),h(h_),d1(d1_),d0(d0_),p(p_){ int sz = a.size(); n = 1; while (n < sz) n <<= 1; val.clear(); val.resize(2 * n - 1, d1); lazy.clear(); lazy.resize(2 * n - 1, d0); for (int i = 0; i < sz; i++) val[i + n - 1] = a[i]; for (int i = n - 2; i >= 0; i--) val[i] = f(val[i * 2 + 1], val[i * 2 + 2]); } inline void eval(int k, int len){ if(lazy[k] == d0) return; if(2*k+1 < 2*n-1){ lazy[2*k+1] = h(lazy[2*k+1], lazy[k]); lazy[2*k+2] = h(lazy[2*k+2], lazy[k]); } val[k] = g(val[k], p(lazy[k], len)); lazy[k] = d0; } void update(int a, int b, E x, int k=0, int l=0, int r=-1){ // 0-indexed // [a,b)に対して操作 if(r < 0) r = n; eval(k, r-l); if(r <=a || b <= l) return; if(a <= l && r <= b){ lazy[k] = h(lazy[k], x); eval(k, r-l); } else{ update(a, b, x, 2*k+1, l, (l+r)/2); update(a, b, x, 2*k+2, (l+r)/2, r); val[k] = f(val[2*k+1], val[2*k+2]); } } T query(int a, int b, int k=0, int l=0, int r=-1){ // 0-indexed // [a,b)に対してquery if(r < 0) r = n; eval(k, r-l); if(r <= a || b <= l) return d1; if(a <= l && r <= b) return val[k]; T val_l = query(a, b , 2*k+1, l, (l+r)/2); T val_r = query(a, b , 2*k+2, (l+r)/2, r); return f(val_l, val_r); } }; void Main(){ auto f = [](P a, P b){return P(a.first+b.first, a.second+b.second);}; auto g = [](P a, P b){ ll x=b.first, len=b.second; return P(a.first+2*a.second*x+x*x*len,a.second+x*len); }; auto h = [](ll a, ll b){return a+b;}; auto p = [](ll a, ll len){return P(a,len);}; int N; cin >> N; vector<P> A(N); REP(i,N){cin >> A[i].second; A[i].first=A[i].second*A[i].second;} LazySegmentTree<P,ll> st(A,f,g,h,P(0,0),(ll)0,p); int Q; cin >> Q; REP(_,Q){ int t; cin >> t; if(t == 1){ int l,r,x; cin >> l >> r >> x; l--; st.update(l,r,x); } else{ int l,r; cin >> l >> r; l--; ll ans = st.query(l,r).first; cout << ans << en; } } return; } int main(void){ cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);cout<<fixed<<setprecision(15); int t=1; //cin>>t; REP(_,t) Main(); return 0; }