最大连续和（POJ2750）

Description

给出一个含有N个结点的环，编号分别为1..N，环上的点带有权值（可正可负），现要动态的修改某个点的权值，求每次修改后环上的最大连续和，但不能是整个序列的和。

Input

第一行为一个整数N(4<=N<=100000)；

第二行为N个用空格分开的整数；

第三行为一个整数M(4<=M<=100000)，表示修改的次数(绝对值小于等于1000)；

接下来M行，每行两个整数A和B(-1000<=B<=1000)，表示将序列中的第A个数的值，修改为B。

Output

对于每个修改，输出修改后环上的最大连续和。

思路

很明显，是在GSS3上面变成了环形的。

所以说考虑断环为链。

也就是答案可以是1~n的最大也可能是总和-1~n的最小。

比较一个最大。

做完了。

#include <bits/stdc++.h>
using namespace std;
const long long N = 500010;
long long n,m;
long long w[N];
struct owl{
    long long l,r;
    long long sum,lmax,rmax,tmax;
}tr[N * 4];
void pushup(owl & u,owl & l, owl & r){
    u.sum = l.sum + r.sum;
    u.lmax = max(l.lmax, l.sum + r.lmax);
    u.rmax = max(r.rmax, r.sum + l.rmax);
    u.tmax = max(max(l.tmax, r.tmax), l.rmax + r.lmax);
}
void pushup(long long u){
    pushup(tr[u],tr[u << 1],tr[u << 1 | 1]);
}
void build(long long u,long long l,long long r){
    if (l == r){
        tr[u] = {l,r,w[r],w[r],w[r],w[r]};
    }
    else{
        tr[u] = {l,r};
        long long mid = l + r >> 1;
        build(u << 1,l,mid),build(u << 1 | 1,mid + 1,r);
        pushup(u);
    }
}
void modify(long long u,long long x,long long v){
    if (tr[u].l == x && tr[u].r == x){
        tr[u] = {x,x,v,v,v,v};
    }
    else{
        long long mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid){
           modify(u << 1,x,v); 
        }
        else{
            modify(u << 1 | 1,x,v);
        }
        pushup(u);
    }
}
owl query(long long u,long long l,long long r){
    if (tr[u].l >= l && tr[u].r <= r){
        return tr[u];
    }
    else{
        long long mid = tr[u].l + tr[u].r >> 1;
        if (r <= mid){
            return query(u << 1,l,r);
        }
        else if (l > mid){
            return query(u << 1 | 1,l,r);
        }
        else{
            auto left = query(u << 1,l,r);
            auto right = query(u << 1 | 1,l,r);
            owl res;
            pushup(res,left,right);
            return res;
        }
    }
}
owl tr2[N * 4];
void pushup2(owl & u,owl & l, owl & r){
    u.sum = l.sum + r.sum;
    u.lmax = max(l.lmax, l.sum + r.lmax);
    u.rmax = max(r.rmax, r.sum + l.rmax);
    u.tmax = max(max(l.tmax, r.tmax), l.rmax + r.lmax);
}
void pushup2(long long u){
    pushup2(tr2[u],tr2[u << 1],tr2[u << 1 | 1]);
}
void build2(long long u,long long l,long long r){
    if (l == r){
        tr2[u] = {l,r,-w[r],-w[r],-w[r],-w[r]};
    }
    else{
        tr2[u] = {l,r};
        long long mid = l + r >> 1;
        build2(u << 1,l,mid),build2(u << 1 | 1,mid + 1,r);
        pushup2(u);
    }
}
void modify2(long long u,long long x,long long v){
    if (tr2[u].l == x && tr2[u].r == x){
        tr2[u] = {x,x,v,v,v,v};
    }
    else{
        long long mid = tr2[u].l + tr2[u].r >> 1;
        if (x <= mid){
           modify2(u << 1,x,v); 
        }
        else{
            modify2(u << 1 | 1,x,v);
        }
        pushup2(u);
    }
}
owl query2(long long u,long long l,long long r){
    if (tr2[u].l >= l && tr2[u].r <= r){
        return tr2[u];
    }
    else{
        long long mid = tr2[u].l + tr2[u].r >> 1;
        if (r <= mid){
            return query2(u << 1,l,r);
        }
        else if (l > mid){
            return query2(u << 1 | 1,l,r);
        }
        else{
            auto left = query2(u << 1,l,r);
            auto right = query2(u << 1 | 1,l,r);
            owl res;
            pushup2(res,left,right);
            return res;
        }
    }
}
int main(){
    cin >> n;
    long long s = 0; 
    for (long long i = 1; i <= n; i ++ ){
        cin >> w[i];
    	s += w[i];
	}
    build(1,1,n);
    build2(1,1,n);
    long long k,x,y;
    cin >> m;
    while (m -- ){
        cin >> x >> y;
        s = s + y - w[x];
        w[x] = y;
        modify(1,x,y);
        modify2(1,x,-y);
    	int a = query(1,1,n - 1).tmax,b = s + query2(1,1,n - 1).tmax,c = query(1,2,n).tmax,d = s + query2(1,2,n).tmax;
		cout << max({a,b,c,d}) << endl;
    }
    return 0;
}