题意：有一个环，有1~N编号，m次操作，将a位置的值改为b，问你这个环当前最小连续和多少（不能全取也不能不取）
思路：用线段树维护一个区间最值连续和。我们设出两个变量Lmin，Rmin，Mmin表示区间左边最小连续和，右边最小连续和，区间最小连续和，显然这可以通过这个方式更新维护。
现在我们已经可以维护一个区间最值连续和了，那么怎么求“环”的最小连续和呢？显然如果最小区间横跨1和n是不能表示出来的（比如最小区间是2，1，n，n-1之和），那么我们可以转化为求sum-Mmax即区间和减去区间最大值，那么显然最终答案是min( sum[1] - Mmax[1], Mmin[1] )，但由题意“不能全取也不能不取”，那么特判。
好久没做线段树维护连续区间的题了...
代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<stdio.h>
#include<string.h>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#include<vector>
using namespace std;
#define inf 0x3f3f3f3f
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define mem(a,b) memset(a,b,sizeof(a));
#define lowbit(x) x&-x;
typedef long long ll;
typedef unsigned long long ull;
const double eps = 1e-;
const int maxn = 1e5+;
const ll mod = 1e8+;
ll Lmax[maxn << ], Rmax[maxn << ], Mmax[maxn << ], sum[maxn << ];
ll Lmin[maxn << ], Rmin[maxn << ], Mmin[maxn << ];
ll a[maxn];
void push_up(int rt){
Lmax[rt] = max(Lmax[rt << ], sum[rt << ] + Lmax[rt << | ]);
Rmax[rt] = max(Rmax[rt << | ], sum[rt << | ] + Rmax[rt << ]);
Mmax[rt] = max(max(Mmax[rt << ], Mmax[rt << | ]), Rmax[rt << ] + Lmax[rt << | ]);
Lmin[rt] = min(Lmin[rt << ], sum[rt << ] + Lmin[rt << | ]);
Rmin[rt] = min(Rmin[rt << | ], sum[rt << | ] + Rmin[rt << ]);
Mmin[rt] = min(min(Mmin[rt << ], Mmin[rt << | ]), Rmin[rt << ] + Lmin[rt << | ]);
sum[rt] = sum[rt << ] + sum[rt << | ];
}
void build(int l, int r, int rt){
if(l == r){
Mmax[rt] = Rmax[rt] = Lmax[rt] = Mmin[rt] = Rmin[rt] = Lmin[rt] = sum[rt] = a[l];
return;
}
int m = (l + r) >> ;
build(l, m, rt << );
build(m + , r, rt << | );
push_up(rt);
}
void update(int pos, int l, int r, int v, int rt){
if(l == r){
Mmax[rt] = Rmax[rt] = Lmax[rt] = Mmin[rt] = Rmin[rt] = Lmin[rt] = sum[rt] = v;
return;
}
int m = (l + r) >> ;
if(pos <= m)
update(pos, l, m, v, rt << );
else
update(pos, m + , r, v, rt << | );
push_up(rt);
}
int main(){
int n, m, A;
ll B;
while(~scanf("%d", &n)){
for(int i = ; i <= n; i++){
scanf("%lld", &a[i]);
}
build(, n, );
scanf("%d", &m);
while(m--){
ll MAX, MIN, ans;
scanf("%d%lld", &A, &B);
update(A, , n, B, );
if(Mmax[] == sum[]){
ans = Mmin[];
}
else if(Mmin[] == sum[]){
ans = Mmin[] - Mmax[];
}
else{
ans = min(sum[] - Mmax[], Mmin[]);
}
printf("%lld\n", ans);
}
}
return ;
}