题目链接:
题意:
题解:
线段树，区间更新（加/减），区间查询最大值
代码:
1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 using namespace std; 5 typedef long long ll; 6 #define MS(a) memset(a,0,sizeof(a)) 7 #define MP make_pair 8 #define PB push_back 9 const int INF = 0x3f3f3f3f; 10 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL; 11 inline ll read(){ 12 ll x=0,f=1;char ch=getchar(); 13 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 14 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 15 return x*f; 16 } 17 ////////////////////////////////////////////////////////////////////////// 18 const int maxn = 1e5+10; 19 20 ll a[maxn]; 21 22 struct node{ 23 int l,r; 24 ll mx,lazy; 25 void update(ll val){ 26 mx = val+mx; 27 lazy += val; 28 } 29 }tree[maxn<<2]; 30 31 void pushup(int rt){ 32 tree[rt].mx = max(tree[rt<<1].mx, tree[rt<<1|1].mx); 33 } 34 35 void pushdown(int rt){ 36 int lazyval = tree[rt].lazy; 37 if(lazyval){ 38 tree[rt<<1].update(lazyval); 39 tree[rt<<1|1].update(lazyval); 40 tree[rt].lazy = 0; 41 } 42 } 43 44 void build(int rt, int l, int r){ 45 tree[rt].l = l, tree[rt].r = r; 46 tree[rt].mx = 0, tree[rt].lazy = 0; 47 if(l == r){ 48 tree[rt].mx = a[l]; 49 }else{ 50 int mid = (l+r)/2; 51 build(rt<<1,l,mid); 52 build(rt<<1|1,mid+1,r); 53 pushup(rt); 54 } 55 } 56 57 void update(int rt,int l,int r,ll val){ 58 int L = tree[rt].l, R = tree[rt].r; 59 if(l<=L && R<=r){ 60 tree[rt].update(val); 61 }else{ 62 pushdown(rt); 63 int mid = (L+R)/2; 64 if(l <= mid) update(rt<<1,l,r,val); 65 if(r > mid) update(rt<<1|1,l,r,val); 66 pushup(rt); 67 } 68 } 69 70 ll query(int rt,int l,int r){ 71 int L = tree[rt].l, R = tree[rt].r; 72 if(l<=L && R<=r){ 73 return tree[rt].mx; 74 }else{ 75 ll ans = 0; 76 pushdown(rt); 77 int mid = (L+R)/2; 78 if(r<=mid)return query(rt<<1,l,r); 79 else if(l>mid)return query(rt<<1|1,l,r); 80 else return max(query(rt<<1,l,mid),query(rt<<1|1,mid+1,r)); 81 } 82 } 83 /* 这样就WA */ 84 // ll query(int rt,int l,int r){ 85 // int L = tree[rt].l, R = tree[rt].r; 86 // if(l<=L && R<=r) 87 // return tree[rt].v; 88 // else{ 89 // ll ans = 0; 90 // pushdown(rt); 91 // int mid = (L+R)/2; 92 // if(l <= mid) ans = max(ans,query(rt<<1,l,r)); 93 // if(r > mid) ans = max(ans,query(rt<<1|1,l,r)); 94 // pushup(rt); 95 // return ans; 96 // } 97 // } 98 99 int main(){ 100 int n=read(),q; 101 for(int i=1; i<=n; i++) 102 a[i] = read(); 103 build(1,1,n); 104 q = read(); 105 while(q--){ 106 int op,a,b,v; 107 op = read(); 108 if(op == 1){ 109 a=read(),b=read(),v=read(); 110 update(1,a,b,v); 111 }else{ 112 a=read(),b=read(); 113 ll ans = query(1,a,b); 114 printf("%lld ",ans); 115 } 116 } 117 118 return 0; 119 }