题目链接：点击打开链接

题目大意：给出n个数排成一个环。求环的最大连续子序列，不能是总序列

建一个线段树来求最大子序列假设仅仅是一个序列。那么求最大连续子序列非常easy，可是假设是一个环，那就要考虑断点的问题，由于结果可能是由左边一部分+右边一部分，这种结果用线段树没法统计到，所以须要转换一下：

求最大连续子序列 = 总和 - 最小连续子序列

那么题目就非常easy了，要统计出每一段的最大连续子序列，最小连续子序列和总和。

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) ;

    else

        update(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]) ;

            else

                printf("%d\n", max(max1[1],sum[1]-min1[1])) ;

        }

    }

    return 0 ;

}