给一个序列a，要得到两个数列b和c，使bi+ci=ai，且b序列递增，c序列递减，要使b和c中最大元素最小。同时会有q次修改，每次将a序列在(l,r)区间内的元素都加上x。
首先由于b和c的性质，所以使b和c中最大元素最小，即是使max(bn,c1)最小。然后我们假设c1已确定，这样b1就也被确定，考虑能否确定b2和c2。由于要使bn最小，所以尽量使每个bi - bi-1尽量小，由于ai和ai-1已经固定，所以(bi - bi-1)+(ci - ci-1)已固定，等同于使ci-1 - ci尽量小。那么每次我们要么使bi=bi-1，要么使ci=ci-1。于是显然，当ai<ai-1时，使ci=ci-1(ci不能大于ci-1);否则使bi=bi-1。这样我们容易发现，一旦确定了c1，其实bn就是确定的了。
我们进而又发现，在上述推导过程中，其实最开始c1的值并不影响我们每次选择bi=bi-1或是ci=ci-1，也不影响bi+ci的和已确定，也就是说每个bi - bi-1(或者说ci - ci-1)的差是确定的，c1减少多少，最后bn增加多少。所以我们一开始可以随便给c1一个值，推出一个bn，得到他们的和，除以二取较大数即为答案。
我们需要记录a序列，第一次做的时候算一次b和c序列，此后只需维护b和c的相邻元素差，记为delb、delc（我令delb[i]=b[i]-b[i-1]，而delc[i]=c[i-1]-c[i]）。蒟蒻用了线段树来记a序列的值。每一次修改，我们先处理左端点。取w1=al-1，w2=al。如果改前w1<w2: 1.改后仍w1<w2, 那么仍是使cl=cl-1，只需sum(就是c1+bn)加x，delb[l]+x 2.改后w1>=w2，那么要改使bl=bl-1,sum要减去delb[l]，delc[l]=-delb[l]-x（x一定为负数），delb[l]=0. 而如果改前w1>=w2: 1.改后仍有该大小关系，sum不受影响（我们是要bn最小，而此时bl一直等于bl-1，所以不变），只需delc[l]减x 2.改后w1<w2，则令cl=cl-1，sum要加上x-delc[l]，delb[l]=x-delc[l]，delc[l]=0 特别地，如果l=1，那显然直接sum+=x。
关于右端点的处理自己推一下吧w 可以参考下面的代码。特别地，如果右端点为n，那么不会引起任何后续变化，所以不需要处理了哦。
每次输出的时候注意一下sum是正是负吧，除以二后取的规则可能不太一样呢qwq
貌似分析了很多显然的东西。
貌似可以不用线段树，我太蒻了。
#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const int N=100010; int n,q,l,r; ll sum,w1,w2,x,a1[N],b1[N],c1[N],delb[N],delc[N],tree[N*4]; inline int read(){ int x=0,f=0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return f?-x:x; } inline void new1(int p,ll f){tree[p]+=f;} inline void pushdown(int p){ if(tree[p]){new1(p<<1,tree[p]);new1(p<<1|1,tree[p]);tree[p]=0;} } ll query(int p,int pa,int pb,int x){ if(pa==pb)return tree[p]; pushdown(p); int mid=(pa+pb)>>1; if(x<=mid)return query(p<<1,pa,mid,x); else return query(p<<1|1,mid+1,pb,x); } void add(int p,int pa,int pb,int a,int b,ll x){ if(a<=pa&&pb<=b){new1(p,x);return;} int mid=(pa+pb)>>1; if(a<=mid)add(p<<1,pa,mid,a,b,x); if(mid<b)add(p<<1|1,mid+1,pb,a,b,x); } void build(int p,int a,int b){ if(a==b){tree[p]=a1[a];return;} tree[p]=0; int mid=(a+b)>>1; build(p<<1,a,mid);build(p<<1|1,mid+1,b); } int main(){ n=read(); for(int i=1;i<=n;++i)a1[i]=1ll*read(); build(1,1,n); b1[1]=a1[1],c1[1]=0; for(int i=2;i<=n;++i){ if(a1[i]>a1[i-1])c1[i]=c1[i-1],b1[i]=a1[i]-c1[i]; else b1[i]=b1[i-1],c1[i]=a1[i]-b1[i]; } for(int i=2;i<=n;++i)delb[i]=b1[i]-b1[i-1],delc[i]=c1[i-1]-c1[i]; q=read(),sum=b1[n]+c1[1]; if(sum>=0)printf("%lld\n",(sum+1)/2); else printf("%lld\n",sum/2); for(int i=1;i<=q;++i){ l=read(),r=read(),x=1ll*read(); if(l!=1){ w1=query(1,1,n,l-1);w2=query(1,1,n,l); if(w2>w1){ if(w2+x<=w1)sum-=delb[l],delc[l]=-delb[l]-x,delb[l]=0; else sum+=x,delb[l]+=x; }else{ if(w2+x>w1)sum+=x-delc[l],delb[l]=x-delc[l],delc[l]=0; else delc[l]-=x; } }else sum+=x; if(r!=n){ w1=query(1,1,n,r);w2=query(1,1,n,r+1); if(w2>w1){ if(w2<=w1+x)sum-=delb[r+1],delc[r+1]=x-delb[r+1],delb[r+1]=0; else sum-=x,delb[r+1]-=x; }else{ if(w2>w1+x)sum-=x+delc[r+1],delb[r+1]=-delc[r+1]-x,delc[r+1]=0; else delc[r+1]+=x; } } add(1,1,n,l,r,x); if(sum>=0)printf("%lld\n",(sum+1)/2); else printf("%lld\n",sum/2); } return 0; }
