Codeforces ECR #133 : E. Swap and Maximum Block

6問回で意外にすんなり解けた回。
https://codeforces.com/contest/1716/problem/E

問題

2^N要素の整数列Aが与えられる。
以下のクエリに順次答えよ。

• 整数kが与えられるので、A[i]とA[i+(2^k)]をswapせよ。(ただし1度swapした箇所は、2度swapしない)
• その後、連続部分列のうち総和の最大値を答えよ

解法

前処理として、以下をkの小さい順に求めて行こう。
kに対し、nは2^(N-k)通り、maskはk通りあるので、状態としては全体でO(N*2^N)通り考えればよい。

L(k,n,mask) := 2進数でk bit目以上の要素がnであり、k bit未満の各bitにおけるswapの有無がmaskであるような数列における、prefix sumの最大値
R(k,n,mask) := 同suffix sumの最大値
S(k,n,mask) := 同数列の総和
M(k,n,mask) := 同数列内の部分列の総和の最大値

あとは各クエリに対し、各bitにおけるswapの有無を更新していけばよい。

int N,Q;
ll L[19][1<<18];
ll R[19][1<<18];
ll S[19][1<<18];
ll ma[19][1<<18];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,(1<<N)) {
		cin>>x;
		L[0][i]=max(0,x);
		R[0][i]=max(0,x);
		S[0][i]=x;
		ma[0][i]=max(0,x);
	}
	for(i=1;i<=N;i++) {
		FOR(j,1<<N) {
			x=j;
			y=j^(1<<(i-1));
			L[i][j]=max(L[i-1][x],S[i-1][x]+L[i-1][y]);
			R[i][j]=max(R[i-1][y],S[i-1][y]+R[i-1][x]);
			S[i][j]=S[i-1][x]+S[i-1][y];
			ma[i][j]=max({ma[i-1][x],ma[i-1][y],R[i-1][x]+L[i-1][y]});
		}
	}
	
	int cur=0;
	cin>>Q;
	while(Q--) {
		cin>>x;
		cur^=1<<x;
		cout<<ma[N][cur]<<endl;
	}
	
}

まとめ

これは割とすんなり思いついたな。