题目链接：点击打开链接
维护区间左起连续的最大和，右起连续的和。。
#include #include #include #include #include #include #include using namespace std; #define N 50050 #define Lson(x) tree[x].l #define Rson(x) tree[x].r #define L(x) (x<<1) #define R(x) (x<<1|1) #define Sum(x) tree[x].sum #define Max(x) tree[x].max #define Lmax(x) tree[x].lmax #define Rmax(x) tree[x].rmax struct node{ int l, r; int mid(){return (l+r)>>1;} int lmax, rmax, max, sum; }tree[N<<4]; int n, a[N], Q; void push_down(int id){} void push_up(int id){ Lmax(id) = max(Lmax(L(id)), Sum(L(id)) + Lmax(R(id))); Rmax(id) = max(Rmax(R(id)), Sum(R(id)) + Rmax(L(id))); Sum(id) = Sum(L(id)) + Sum(R(id)); Max(id) = max(max(Max(L(id)), Max(R(id))), Rmax(L(id)) + Lmax(R(id))); } void updata_point(int val, int id){Lmax(id) = Rmax(id) = Max(id) = Sum(id) = val;} void build(int l, int r, int id){ Lson(id) = l; Rson(id) = r; if(l == r) { updata_point(a[l], id); return; } int mid = tree[id].mid(); build(l, mid, L(id)); build(mid+1, r, R(id)); push_up(id); } void updata(int pos, int val, int id){ push_down(id); if(Lson(id) == Rson(id)) { updata_point(val, id); return ; } int mid = tree[id].mid(); if(mid < pos) updata(pos, val, R(id)); else updata(pos, val, L(id)); } int query_l(int l, int r, int id){ push_down(id); if(l == Lson(id) && Rson(id) == r) return Lmax(id); int mid = tree[id].mid(); if(mid < l) return query_l(l, r, R(id)); else if(r <= mid) return query_l(l, r, L(id)); int lans = query_l(l, mid, L(id)), rans = query_l(mid+1, r, R(id)); return max(lans, Sum(L(id)) + rans); } int query_r(int l, int r, int id){ push_down(id); if(l == Lson(id) && Rson(id) == r) return Rmax(id); int mid = tree[id].mid(); if(mid < l) return query_r(l, r, R(id)); else if(r <= mid) return query_r(l, r, L(id)); int lans = query_r(l, mid, L(id)), rans = query_r(mid+1, r, R(id)); return max(rans, Sum(R(id)) + lans); } int query(int l, int r, int id){ push_down(id); if(l == Lson(id) && Rson(id) == r)return Max(id); int mid = tree[id].mid(); if(mid < l) return query(l, r, R(id)); else if(r<=mid) return query(l, r, L(id)); int lans = query(l, mid, L(id)), rans = query(mid+1, r, R(id)); int ans = max(lans, rans); return max(ans, query_r(l, mid, L(id)) + query_l(mid+1, r, R(id))); } int main(){ while(~scanf("%d",&n)){ for(int i = 1; i <= n; i++)scanf("%d",&a[i]); build(1, n, 1); scanf("%d",&Q); while(Q--){ int l, r; scanf("%d %d",&l,&r); printf("%d\n", query(l, r, 1)); } } return 0; } /* 3 -1 2 3 1 1 2 */