本文主要是介绍poj2750--Potted Flower(线段树)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：点击打开链接
题目大意：给出n个数排成一个环，求环的最大连续子序列，不能是总序列
建一个线段树来求最大子序列如果只是一个序列，那么求最大连续子序列很简单，但是如果是一个环，那就要考虑断点的问题，因为结果可能是由左边一部分+右边一部分，这样的结果用线段树没法统计到，所以需要转换一下：
求最大连续子序列 = 总和 - 最小连续子序列
那么题目就很简单了，要统计出每一段的最大连续子序列，最小连续子序列和总和。
sum[rt] = sum[rt<<1] + sum[rt<<1|1] ;
max1[rt] = max( max(max1[rt<<1],max1[rt<<1|1]),rmax1[rt<<1]+lmax1[rt<<1|1] ) ; 最大连续子序列
min1[rt] = min( min(min1[rt<<1],min1[rt<<1|1]),rmin1[rt<<1]+lmin1[rt<<1|1] ) ; 最小连续子序列
lmax1[rt] = max(lmax1[rt<<1],sum[rt<<1]+lmax1[rt<<1|1]) ; 以左侧开头的最大子序列
lmin1[rt] = min(lmin1[rt<<1],sum[rt<<1]+lmin1[rt<<1|1]) ; 以左侧开头的最小子序列
rmax1[rt] = max(rmax1[rt<<1|1],sum[rt<<1|1]+rmax1[rt<<1]) ; 以右侧开头的最大子序列
rmin1[rt] = min(rmin1[rt<<1|1],sum[rt<<1|1]+rmin1[rt<<1]) ; 以右侧开头的最小子序列
有因为不能是全部的序列，那么可以分开考虑，如果全都是整数，最大连续子序列是总和，那么结果应该是总和-最小连续子序列，如果全是负数，那么结果应该是最大连续子序列，其他的为 max(max1[1],sum[1]-min1[1]))
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
#define root 1,n,1
#define int_rt int l,int r,int rt
#define lson l,(l+r)/2,rt<<1
#define rson (l+r)/2+1,r,rt<<1|1
int cl[1000000] , sum[1000000] ;
int max1[1000000] , min1[1000000] ;
int lmax1[1000000] , lmin1[1000000] ;
int rmax1[1000000] , rmin1[1000000] ;
void push_up(int rt) {sum[rt] = sum[rt<<1] + sum[rt<<1|1] ;max1[rt] = max( max(max1[rt<<1],max1[rt<<1|1]),rmax1[rt<<1]+lmax1[rt<<1|1] ) ;min1[rt] = min( min(min1[rt<<1],min1[rt<<1|1]),rmin1[rt<<1]+lmin1[rt<<1|1] ) ;lmax1[rt] = max(lmax1[rt<<1],sum[rt<<1]+lmax1[rt<<1|1]) ;lmin1[rt] = min(lmin1[rt<<1],sum[rt<<1]+lmin1[rt<<1|1]) ;rmax1[rt] = max(rmax1[rt<<1|1],sum[rt<<1|1]+rmax1[rt<<1]) ;rmin1[rt] = min(rmin1[rt<<1|1],sum[rt<<1|1]+rmin1[rt<<1]) ;
}
void creat(int_rt) {if( l == r ) {scanf("%d", &cl[rt]) ;sum[rt] = max1[rt] = min1[rt] = lmax1[rt] = lmin1[rt] = rmax1[rt] = rmin1[rt] = cl[rt] ;return ;}creat(lson) ;creat(rson) ;push_up(rt) ;
}
void update(int k,int s,int_rt) {if( l == r ) {cl[rt] = s ;sum[rt] = max1[rt] = min1[rt] = lmax1[rt] = lmin1[rt] = rmax1[rt] = rmin1[rt] = cl[rt] ;return ;}if( (l+r)/2 >= k )update(k,s,lson) ;elseupdate(k,s,rson) ;push_up(rt) ;
}
int main() {int n , m , i , k , s ;while( scanf("%d", &n) != EOF ) {creat(root) ;scanf("%d", &m) ;while( m-- ) {scanf("%d %d", &k, &s) ;update(k,s,root) ;if( max1[1] == sum[1] )printf("%d\n", sum[1]-min1[1]) ;else if( min1[1] == sum[1] )printf("%d\n", max1[1]) ;elseprintf("%d\n", max(max1[1],sum[1]-min1[1])) ;}}return 0 ;
}
这篇关于poj2750--Potted Flower(线段树)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
