题目
小(A)和小(B)在一个长度为(2n)的数组上面博弈，初始时奇数位置为A，偶数位置为B
小(A)先手，第(i)次操作的人可以将(i)或者(i+1)位置的值反转(也可以不做任何操作)
(n-1)次操作结束后，小(A)得分为所有(A)位置的权值和，小(B)同理
每次会把一个权值改小，询问每次小A得到的和
$n le 200000 $，权值为非负数
题解
-
设(f_{i,0/1})表示从(i)位置向后考虑，(i)位置有没有反转，当前操作的人和另一个人得分差值的最大值
[egin{align} &egin{cases} f_{i,0} &= max { s_i - f_{i+1,0} , s_i - f_{i+1,1} } \ f_{i,1} &= max { s_i - f_{i+1,0} ,-s_i - f_{i+1,1} } \ end{cases}\ &设Delta _i = f_{i,0} - f_{i,1} \ &由于s_ige 0 显然Delta_i ge 0\ &egin{cases} f_{i,0} &= s_i - f_{i+1,1} \ f_{i,1} &= max { 2s_i - Delta_{i+1} , 0 } - s_i - f_{i+1,1} \ Delta_i &= min { 2s_i , Delta_{i+1} } end{cases}\ &Delta_n=2s_n 维护 Delta_i 也就是对2s_i 取后缀min \ &f_{1,0} = sum_{i=1}^{n}(-1)^{i-1}s_i + sum_{i=2}^{n} (-1)^i Delta_{i} \ end{align} ] -
维护后缀(min)值只有改小的话可以在线段树上先二分再修改，时间复杂度(O(n log n))
-
没有这个条件可以用线段树维护从前往后递增的单调栈
-
具体来说每段区间维护最小值(mn)和区间答案(sum)
-
考虑当前区间(K)的左右儿子为(L,R)，左儿子(L)的左右儿子为(l,r)
如果 $mn_{R} lt mn_{r} $ ，右区间的贡献都为(mn_R)，直接统计，并递归(l)
如果 $ mn_R ge mn_r $ ，记录$ add_K (表示用)K(的左儿子的mn走右儿子的答案，直接统计)add_K (并递归)r$
时间复杂度：$O(n log ^2n ) $
#include<bits/stdc++.h> #define ll long long #define ls (k<<1) #define rs (k<<1|1) using namespace std; char gc(){ static char*p1,*p2,s[1000000]; if(p1==p2)p2=(p1=s)+fread(s,1,1000000,stdin); return(p1==p2)?EOF:*p1++; } int rd(){ int x=0;char c=gc(); while(c<'0'||c>'9')c=gc(); while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0',c=gc(); return x; } const int N=200010; int n,m,s[N]; ll tmp,Mn,mn[N<<2],sum[N<<2],add[N<<2],ans; ll sg(int l,int r,int x){return ((r-l)&1)?0:l&1?-x:x;} void mfy(int k,int l){mn[k]=s[l];sum[k]=l&1?-s[l]:s[l];} void cal(int k,int l,int r){ if(l==r){tmp+=sg(l,r,min(Mn,mn[k]));return;} int mid=(l+r)>>1; if(Mn<mn[rs])tmp+=sg(mid+1,r,Mn),cal(ls,l,mid); else tmp+=add[k],cal(rs,mid+1,r); } void pushup(int k,int l,int r){ mn[k]=min(mn[ls],mn[rs]); int mid=(l+r)>>1; tmp=0;Mn=mn[rs]; cal(ls,l,mid); sum[k]=sum[rs]+(add[k]=tmp); } void build(int k,int l,int r){ if(l==r){mfy(k,l);return;} int mid=(l+r)>>1; build(ls,l,mid); build(rs,mid+1,r); pushup(k,l,r); } void update(int k,int l,int r,int x){ if(l==r){mfy(k,l);return;} int mid=(l+r)>>1; if(x<=mid)update(ls,l,mid,x); else update(rs,mid+1,r,x); pushup(k,l,r); } int main(){ freopen("flip.in","r",stdin); freopen("flip.out","w",stdout); n=rd(); for(int i=1;i<=n;++i){s[i]=rd();if(i&1)ans+=s[i];} build(1,2,n); printf("%lld ",ans+sum[1]); m=rd(); for(int i=1;i<=m;++i){ int x=rd(),y=rd(); if(x&1)ans-=s[x]; s[x]-=y;if(x&1)ans+=s[x]; if(x>1)update(1,2,n,x); printf("%lld ",ans+sum[1]); } return 0; }