結果
問題 | 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)に対してqueryif(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;}