CODE FESTIVAL 2017 Elimination Tournament : C - Paired Parentheses

Round1は自力でどうにかなったけど、それ以降はダメダメ。
https://cf17-tournament-round1-open.contest.atcoder.jp/tasks/asaporo2_c

問題

2N要素の２つの整数列A,Bが与えられる。
2N文字の正しい括弧列S,Tがあったとき、文字の各位置iに関し両者が一致するならA[i]、異なるならB[i]の得点を得るものとする。
この際最適なS,Tを選んだ時の最高総得点を求めよ。

また、A,Bを1要素書き換えるクエリが与えられるので、適宜S,Tを任意に選んだ時の最高総得点を求めよ。

解法

厳密な証明はEditorialを参照いただくとして、実は最初の１文字と最後の１文字以外は両者を一致させることも異なるようにすることもできる。
ただし正しい括弧列を満たすため、異なってよい文字は偶数個である。

よって先頭と末尾を除きB[i]-A[i]を並べて大きい順に偶数個とっていくことを考えよう。
B[i]-A[i]が正となるものが偶数個なら何も考える必要はないし、奇数個ならB[i]-A[i]が正の物のうち最小値をあきらめるか、もしくはB[]-A[i]が0以下の物のうち最大値を取り込むかどちらかである。
あとはB[i]-A[i]が正の物とそうでないものをmultiset等で管理していけばよい。

int N,Q;
int A[201010];
int B[201010];
multiset<int> p,n;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	ll S=0,T=0;
	FOR(i,2*N) cin>>A[i], S+=A[i];
	FOR(i,2*N) {
		cin>>B[i];
		B[i]-=A[i];
		if(i!=0 && i!=2*N-1) {
			if(B[i]>0) {
				p.insert(B[i]);
				T+=B[i];
			}
			else {
				n.insert(-B[i]);
			}
		}
	}
	while(Q--) {
		cin>>i>>x>>y;
		i--;
		S-=A[i];
		if(i!=0 && i!=2*N-1) {
			if(B[i]>0) {
				p.erase(p.find(B[i]));
				T-=B[i];
			}
			else {
				n.erase(n.find(-B[i]));
			}
		}
		
		A[i]=x;
		S+=x;
		B[i]=y-A[i];
		if(i!=0 && i!=2*N-1) {
			if(B[i]>0) {
				p.insert(B[i]);
				T+=B[i];
			}
			else {
				n.insert(-B[i]);
			}
		}
		
		ll ma=0;
		if(p.size()%2==0) ma=S+T;
		else ma=S+max(T-*p.begin(),T-*n.begin());
		cout<<ma<<endl;
	}
}

まとめ

先頭と末尾以外任意に取れるというのを厳密に証明せず解いてしまったけど、本当は納得したうえで解く方がいいんだろうなぁ。