题意:给定n(4<=n<=100000)个数字组成的环形序列,有m(4<=m<=100000)个操作p,v表示把p位置的数组更改为v,每次更改后求出最大子段和,
但是要求不能所有的数字都被选择。
题解:最大子段和的维护,因为是环形,需要同时维护最小子段和,至于能不能全选,维护最小值判断下即可。
Sure原创,转载请注明出处
#include <iostream> #include <cstdio> #include <memory.h> #define MIN(a , b) ((a) < (b) ? (a) : (b)) #define MAX(a , b) ((a) > (b) ? (a) : (b)) using namespace std; const int inf = 1 << 29; const int maxn = 100002; struct T { int l,r; int min,sum; int lminsum,rminsum,minsum; int lmaxsum,rmaxsum,maxsum; }seg[maxn << 2]; int n,m; void biuld(int l,int r,int num) { seg[num].l = l; seg[num].r = r; if(l == r) return; int mid = (l + r) >> 1; biuld(l , mid , num << 1); biuld(mid + 1 , r , num << 1 | 1); return; } void UP(int num) { seg[num].sum = seg[num << 1].sum + seg[num << 1 | 1].sum; seg[num].min = MIN(seg[num << 1].min , seg[num << 1 | 1].min); seg[num].lmaxsum = MAX(seg[num << 1].sum + seg[num << 1 | 1].lmaxsum , seg[num << 1].lmaxsum); seg[num].rmaxsum = MAX(seg[num << 1 | 1].sum + seg[num << 1].rmaxsum , seg[num << 1 | 1].rmaxsum); seg[num].maxsum = MAX(seg[num << 1].maxsum , seg[num << 1 | 1].maxsum); seg[num].maxsum = MAX(seg[num].maxsum , MAX(seg[num].lmaxsum , seg[num].rmaxsum)); seg[num].maxsum = MAX(seg[num].maxsum , seg[num << 1].rmaxsum + seg[num << 1 | 1].lmaxsum); seg[num].lminsum = MIN(seg[num << 1].sum + seg[num << 1 | 1].lminsum , seg[num << 1].lminsum); seg[num].rminsum = MIN(seg[num << 1 | 1].sum + seg[num << 1].rminsum , seg[num << 1 | 1].rminsum); seg[num].minsum = MIN(seg[num << 1].minsum , seg[num << 1 | 1].minsum); seg[num].minsum = MIN(seg[num].minsum , MIN(seg[num].lminsum , seg[num].rminsum)); seg[num].minsum = MIN(seg[num].minsum , seg[num << 1].rminsum + seg[num << 1 | 1].lminsum); return; } void update(int pos,int val,int num) { if(seg[num].l == seg[num].r) { seg[num].min = seg[num].sum = val; seg[num].lmaxsum = seg[num].rmaxsum = seg[num].maxsum = MAX(0 , val); seg[num].lminsum = seg[num].rminsum = seg[num].minsum = MIN(0 , val); return; } int mid = (seg[num].l + seg[num].r) >> 1; if(pos <= mid) update(pos , val , num << 1); else update(pos , val , num << 1 | 1); UP(num); return; } void read() { int val; for(int i=1;i<=n;i++) { scanf("%d",&val); update(i , val , 1); } return; } void solve() { scanf("%d",&m); int p,v; while(m--) { scanf("%d %d",&p,&v); update(p , v , 1); if(seg[1].min >= 0) printf("%d\n",seg[1].sum - seg[1].min); else printf("%d\n",MAX(seg[1].maxsum , seg[1].sum - seg[1].minsum)); } return; } int main() { while(~scanf("%d",&n)) { biuld(1,n,1); read(); solve(); } return 0; }