Codeforces #670 Div2 D. Three Sequences

かなりすんなり全完できた回。
https://codeforces.com/contest/1406/problem/D

問題

整数列Aが与えられる。
これを2つの数列B,Cを用いて以下のように表現したい。

• B[i]+C[i]=A[i]
• B[i]は単調増加
• C[i]は単調減少

このとき、max(B,C)を最小化したい。

Aの区間に値Xを足すクエリが与えられる。
その都度、上記max(B,C)の最小値を答えよ。

解法

max(B[N-1],C[0])を最小化する問題となる。
この時、B[N-1]はどうなるかというと、B[0]に対しmax(0,A[i]-A[i-1])の総和を取ったものとなる。
同様に、C[0]はC[N-1]に対しmax(0,A[i-1]-A[i])の総和を取ったものになる。

結局B[0]+C[N-1]=A[0]+sum(|A[i]-A[i-1]|)となるので、解は(A[0]+sum(|A[i]-A[i-1]|))/2となる。
クエリ毎にA[i]-A[i-1]が変化するのは高々2か所なので、クエリ毎に(A[0]+sum(|A[i]-A[i-1]|))の変化分を考えよう。

int N;
ll A[101010];
int Q;
int L,R,X;

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<ll,20> bt;
ll add=0;

void hoge() {
	ll cur=bt(1)+add;
	if(cur>=0) {
		cout<<(cur+1)/2<<endl;
	}
	else {
		cout<<cur/2<<endl;
	}
}



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	int pre=0;
	FOR(i,N) {
		cin>>x;
		bt.add(i+1,x-pre);
		if(i&&x>pre) add+=x-pre;
		pre=x;
	}
	
	hoge();
	cin>>Q;
	FOR(i,Q) {
		cin>>L>>R>>X;
		ll a,b;
		if(L>1) {
			a=bt(L-1);
			b=bt(L);
			if(b>a) add-=b-a;
		}
		if(R+1<=N) {
			a=bt(R);
			b=bt(R+1);
			if(b>a) add-=b-a;
		}
		bt.add(L,X);
		bt.add(R+1,-X);
		if(L>1) {
			a=bt(L-1);
			b=bt(L);
			if(b>a) add+=b-a;
		}
		if(R+1<=N) {
			a=bt(R);
			b=bt(R+1);
			if(b>a) add+=b-a;
		}
		
		hoge();
	}
	
	
}

まとめ

本番なんか謎にBIT使ってるけど、これ要らんな。