OI - Three Sequences（Codeforces）

看到别人去CF出题，然后想要趁没有退役去出一场

---

# 题面

点击展开/折叠 题面

给定序列 $a_1,a_2,\dots,a_n$（$1\le n\le10^5$），对原序列构造出一个非递减序列 $b_1,b_2,\dots,b_n$、一个非递增序列 $c_1,c_2,\dots,c_n$，满足 $\forall_i b_i+c_i=a_i$，使得 $\max\{b_i,c_i\}$ 最小，输出该最小值。

接下来对原序列进行 $m$ 次操作（$1\le m\le10^5$），每次操作对区间 $[l,r]$ 增加 $x$；每次操作后对新的序列求解上述问题。

---

# 解析

显然即要求 $\max\{b_n,c_1\}$ 最小，贪心地想，从左到右依次决策 $b_i$ 的取值，$b_i$ 能不增大则不增大（优先减小 $c$），于是想到对于每种情况讨论最优方案。

如果当前决策到了位置 $i$：

• 若 $a_i\le a_{i-1}$，则 $b_i$ 能够直接取到 $b_{i-1}$，而 $c_i$ 减小到 $a_i-b_{i-1}$；
• 若 $a_i>a_{i-1}$，则 $b_i$ 必须增大，为了增大尽可能小，$c_i$ 直接取到 $c_{i-1}$，而 $b_i=a_i-c_{i-1}$。

再概括一下：

$$\begin{cases} \begin{array}{l} b_i=b_{i-1}\\ c_i=a_i-b_{i-1}=a_i-a_{i-1}+c_{i-1} \end{array}&(a_i\le a_{i-1})\\ \begin{array}{l} b_i=a_i-c_{i-1}=a_i-a_{i-1}+b_i\\ c_i=c_{i-1} \end{array}&(a_i>a_{i-1})\\ \end{cases}$$

---

# 源代码

/*Lucky_Glass*/
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

inline int Read(){
	register int r=0,b=1,c=getchar();
	while(c<'0' || '9'<c) b=c=='-'?-1:b,c=getchar();
	while('0'<=c && c<='9') r=(r<<1)+(r<<3)+(c^'0'),c=getchar();
	return r*b;
}

typedef long long ll;
const int N=1e5+10;
#define lowbit(x) ((x)&(-(x)))

int n,m;
ll tary[N];

void Modify(int pos,ll key){
	while(pos<=n){
		tary[pos]+=key;
		pos+=lowbit(pos);
	}
}
ll Query(int pos){
	ll ret=0;
	while(pos){
		ret+=tary[pos];
		pos-=lowbit(pos);
	}
	return ret;
}
ll Calc(ll a,ll b){return ceil((a+b)/2.0);}
int main(){
	n=Read();
	ll psi=0,neg=0;
	for(int i=1,las=0,now=0;i<=n;i++,las=now){
		now=Read();
		Modify(i,now),Modify(i+1,-now);
		if(i>1) psi+=max(0,now-las),neg+=min(0,now-las);
	}
	printf("%lld\n",Calc(Query(1),psi));
	m=Read();
	while(m--){
		int le=Read(),ri=Read(),key=Read();
		ll tmp;
		if(le>1) tmp=Query(le)-Query(le-1),psi-=max(tmp,0ll),neg-=min(tmp,0ll);
		if(ri<n) tmp=Query(ri+1)-Query(ri),psi-=max(tmp,0ll),neg-=min(tmp,0ll);
		Modify(le,key),Modify(ri+1,-key);
		if(le>1) tmp=Query(le)-Query(le-1),psi+=max(tmp,0ll),neg+=min(tmp,0ll);
		if(ri<n) tmp=Query(ri+1)-Query(ri),psi+=max(tmp,0ll),neg+=min(tmp,0ll);
		printf("%lld\n",Calc(Query(1),max(psi,Query(n)-Query(1)-neg)));
	}
	return 0;
}