Codeforces #755 Div1 : B. Guess the Permutation

なんかこの回は妙に調子いいな。
https://codeforces.com/contest/1588/problem/B

問題

A[n]=nであるN要素の整数列があったとする。
ここに、i＜j＜kとなる3要素を選び、A[i...(j-1)]を反転し、またA[j...k]を反転したとする。
このi,j,kを、以下のクエリを最大40回まで使い求めよ。

• 区間[L,R]を指定すると、A[L...R]の転倒数を答える

解法

A全体の転倒数をIとする。
A[1...n]の転倒数がlとなる最大のnを二分探索で求めれば、kを確定できる。
A[1...k]の転倒数とA[1..(k-1)]の転倒数を求めればA[k]の値が求まり、jの値が求まる。
同様に、A[1...j]とA[1...(j-1)]の転倒数を比較すればiの値が求まる。

int T,N;

ll ask(int L,int R) {
	if(R<=L) return 0;
	cout<<"? "<<L<<" "<<R<<endl;
	ll a;
	cin>>a;
	return a;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		
		cin>>N;
		ll tot=ask(1,N);
		for(i=30;i>=0;i--) {
			ll a=ask(1,N-(1<<i));
			if(tot==a) N-=1<<i;
		}
		ll tot2=ask(1,N-1);
		int R=N;
		int M=N-(tot-tot2)-1;
		
		ll a=ask(1,M);
		ll b=ask(1,M-1);
		int L=M-(a-b);
		cout<<"! "<<L<<" "<<(M+1)<<" "<<R<<endl;
		
		
	}
}

まとめ

1つだけ値を二分探索で求めると、残りはO(1)で決まっていくのは面白いね。