Codeforces ECR #148 : D2. Red-Blue Operations (Hard Version)

EよりDの方が難しい。
https://codeforces.com/contest/1832/problem/D2

問題

N要素の整数列Aが与えられる。
クエリとして整数Kが与えられるのでいかに答えよ。

i=1～Kまで以下を行う。

• Aから1つ要素を選び、i加算又は減算する。その要素を選ぶのが奇数回目なら加算、偶数回目なら減算とする。

Aの最小値の最大値を求めよ。

解法

奇数回選択された要素は初期値より増え、偶数回選択された要素は初期値より減る。
逆向きに考え、小さい要素から順にK,K-1,K-2を足し…とみて行くとよい。
これを累積和など使い高速化する。

int N,Q;
ll A[202020],B[202020];
ll SA[202020],SB[202020];
ll miB[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N) cin>>A[i];
	sort(A,A+N);
	FOR(i,N) {
		miB[i]=B[i]=A[i]-i;
		if(i) miB[i]=min(miB[i],miB[i-1]);
		SA[i+1]=SA[i]+A[i];
		SB[i+1]=SB[i]+B[i];
	}
	while(Q--) {
		ll K;
		cin>>K;
		
		ll ret;
		
		if(N==1) {
			if(K%2==0) {
				ret=A[0]-K/2;
			}
			else {
				ret=A[0]+1+K/2;
			}
		}
		else if(K==N) {
			ret=miB[N-1]+N;
		}
		else if(K<N) {
			ret=min(miB[K-1]+K,A[K]);
		}
		else if(K%2==N%2) {
			ret=miB[N-1]+K;
			K-=N;
			assert(K%2==0);
			K/=2;
			K-=SB[N]-miB[N-1]*N;
			if(K>0) {
				ret-=K/N;
				if(K%N) ret--;
			}
		}
		else {
			ll a=miB[N-2]+K;
			ll b=A[N-1];
			K-=N-1;
			K/=2;
			K-=SB[N-1]-miB[N-2]*(N-1);
			if(a<b) {
				K-=b-a;
			}
			else if(a>b) {
				K-=(a-b)*(N-1);
				a=b;
			}
			ret=a;
			if(K>0) {
				ret-=K/N;
				if(K%N) ret--;
			}
			
		}
		cout<<ret<<" ";
	}
	cout<<endl;
}

まとめ

シンプルな設定ながら場合分けがめんどい。