Codeforces #1052 : Div2. D2. Max Sum OR (Hard Version)

微妙な出来の回。
https://codeforces.com/contest/2146/problem/D2

問題

整数区間[L,R]が指定される。
L...RのPermutationを２つA,Bと作り、sum(A[i] or B[i])を最大化したい。
その最大値と、数列の例を答えよ。

解法

f(L1,R1,L2,R2) := L1...R1のPermutationとL2...R2のPermutationで、bitwise-orの総和が最大となるもの
とする。解をf(L,R,L,R)とし、再帰的に求めて行く。
LとRのMSBが異なる場合、[L...R]のうちMSBが最大のものとそうでないものがペアとなるように対応付ける。
あとはその最大のMSBを除いて再帰的に求めて行けばよい。

int T;
ll L,R;

ll A[202020],B[202020];
int CA[202020],CB[202020];

void dfs(ll cur,ll L,ll R) {
	if(L>=R) return;
	if(L+1==R) {
		B[cur]|=L;
		return;
	}
	ll msb=0;
	int i;
	FOR(i,32) if((R-1)&(1LL<<i)) msb=1LL<<i;
	int a=0;
	for(i=L;i<R;i++) if(i&msb) a++;
	if(a==R-L) {
		for(i=L;i<R;i++) B[cur+i-L]|=msb;
		dfs(cur,L^msb,(L^msb)+R-L);
	}
	else {
		int le=R-L-a;
		if(le<=a) {
			FOR(i,le) {
				B[cur+le+i]|=msb-1-i;
				B[cur+le-1-i]|=msb+i;
			}
			for(i=2*le;i<R-L;i++) B[cur+i]|=msb;
			dfs(cur+2*le,L+2*le,R);
		}
		else {
			FOR(i,a) {
				B[cur+R-L-a+i]|=msb-1-i;
				B[cur+R-L-a-1-i]|=msb+i;
			}
			dfs(cur,L,L+(R-L-2*a));
		}
	}
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>L>>R;
		FOR(i,R-L+1) {
			A[i]=CA[i]=L+i;
			B[i]=0;
		}
		
		dfs(0,L,R+1);
		
		ll ret=0;
		FOR(i,R-L+1) ret+=A[i]|B[i];
		cout<<ret<<endl;
		FOR(i,R-L+1) cout<<B[i]<<" ";
		cout<<endl;
		
	}
}

まとめ

まぁこれは割とすぐ思いつくか。