#include<bits/stdc++.h> #define ll long long using namespace std; const int inf = 0x3f3f3f3f; const int maxn = 1e5 +10; int n, a[maxn], q; struct node{ int l,r; ll sum,lazy; ll mi, mx; void update(ll x){ lazy += x; sum += 1LL*(r-l+1)*x; mi += x; mx += x; } }tree[maxn*4]; void push_up(int x){ tree[x].sum = tree[x<<1].sum + tree[x<<1|1].sum; tree[x].mi = min(tree[x<<1].mi,tree[x<<1|1].mi); tree[x].mx = max(tree[x<<1].mx,tree[x<<1|1].mx); } void push_down(int x){ int lazyval = tree[x].lazy; if(lazyval){ tree[x<<1].update(lazyval); tree[x<<1|1].update(lazyval); tree[x].lazy = 0; } } void build(int x,int l,int r){ //x is root tree[x].l = l, tree[x].r = r; tree[x].sum = tree[x].lazy = 0; tree[x].mi = inf; tree[x].mx = -inf; if(l==r){ tree[x].sum = a[l]; tree[x].mi = a[l]; tree[x].mx = a[l]; }else { int mid = (l+r)/2; build(x<<1,l,mid); build(x<<1|1,mid+1,r); push_up(x); } } void update(int x,int l,int r,ll val){ //x is root int L = tree[x].l, R = tree[x].r; if(l<=L && R <=r){ tree[x].update(val); }else{ push_down(x); int mid =(L+R)/2; if(mid>=l) update(x<<1,l,r,val); if(r>mid) update(x<<1|1,l,r,val); push_up(x); } } void query(int x,int l,int r, ll &qsum, ll &qmin, ll &qmax){ //x is root int L = tree[x].l, R = tree[x].r; if(l<=L && R <=r){ //return tree[x].sum; qsum = tree[x].sum; qmin = tree[x].mi; qmax = tree[x].mx; }else{ push_down(x); //ll ans = 0; ll qlsum = 0, qrsum = 0; ll qlmin = inf, qrmin = inf; ll qlmax = -inf,qrmax = -inf; int mid =(L+R)/2; if(mid>=l) query(x<<1,l,r,qlsum,qlmin,qlmax); if(r>mid) query(x<<1|1,l,r,qrsum,qrmin,qrmax); push_up(x); qsum += qlsum+qrsum; qmin = min(qlmin,qrmin); qmax = max(qlmax,qrmax); //return ans; } } int main() { scanf("%d",&n); for(int i=1; i<=n; i++) scanf("%d",&a[i]); build(1,1,n); scanf("%d",&q); for(int i=1; i<=q; i++){ int l, r, val; scanf("%d%d%d",&l,&r,&val); update(1,l,r,val); ll ans_sum = 0, ans_min = 0, ans_max = 0; query(1,l,r,ans_sum,ans_min,ans_max); printf("%lldn", ans_sum); printf("%lldn", ans_min); printf("%lldn", ans_max); } }
|
近期评论