Codeforces #1049 : Div2. D. A Cruel Segment's Thesis

なんか今回実装が長めな問題が多いな。
https://codeforces.com/contest/2140/problem/D

問題

N個の区間[L[i],R[i]]が与えられる。
初期状態でどの区間もマークされていない。

以下の手順をマークされていない区間がなくなるまで繰り返す。

• マークされていない区間が1個なら、それをマークする。
• マークされていない区間が2個以上ある場合、2個を選んでマークするさらにもう1つ追加でマークした区間を追加する。その際、新たな区間の開始・終了点は、それぞれ元の2つの区間の範囲内でなければならない。

最終的な区間の総長の最大値を求めよ。

解法

元々ある区間はすべて解に計上されるので、あとはどう2個ずつ組にして新たな区間を作るかを考える。

Nが偶数の時を考える。
N/2個R[i]が解に計上され、N/2個-L[i]が解に計上される。
よって、両者の差分-R[i]-L[i]が大きい順にN/2個を後者とする世にすればよい。

Nが奇数の場合、1個だけは他の区間とペアにならない。
そのうえで、その1個を総当たりしつつ、残りの(N-1)個の区間について、上記-R[i]-L[i]の大きな順(N-1)/2個の総和を求めよう。

int T,N;
ll L[202020],R[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		ll sum=0;
		cin>>N;
		FOR(i,N) {
			cin>>L[i]>>R[i];
			sum+=R[i]-L[i];
		}
		
		if(N%2==0) {
			vector<ll> A;
			FOR(i,N) {
				sum+=R[i];
				A.push_back(-L[i]-R[i]);
			}
			sort(ALL(A));
			reverse(ALL(A));
			FOR(i,N/2) sum+=A[i];
		}
		else if(N>2) {
			multiset<ll> le,mo;
			ll mos=0,ts=0;
			ll dif=0;
			for(i=1;i<N;i++) {
				ts+=R[i];
				le.insert(-L[i]-R[i]);
			}
			FOR(i,N/2) {
				ll a=*le.rbegin();
				le.erase(le.find(a));
				mo.insert(a);
				mos+=a;
			}
			dif=ts+mos;
			for(i=1;i<N;i++) {
				ll a=-L[i]-R[i];
				ll b=-L[i-1]-R[i-1];
				ts-=R[i];
				ts+=R[i-1];
				if(mo.find(a)!=mo.end()) {
					mo.erase(mo.find(a));
					mos-=a;
				}
				else {
					le.erase(le.find(a));
				}
				le.insert(b);
				if(le.size()==N/2) {
					if(*le.rbegin()>*mo.begin()) {
						ll a=*le.rbegin();
						le.erase(le.find(a));
						mo.insert(a);
						mos+=a;
						a=*mo.begin();
						mo.erase(mo.find(a));
						mos-=a;
						le.insert(a);
					}
				}
				else {
					ll a=*le.rbegin();
					le.erase(le.find(a));
					mo.insert(a);
					mos+=a;
				}
				dif=max(dif,ts+mos);
			}
			
			
			sum+=dif;
		}
		cout<<sum<<endl;
	}
}

まとめ

なんか妙に手間取った。