Codeforces #1061 : Div2. D2. Diadrash (Hard Version)

最初からHardを解きに行ってるな…。
https://codeforces.com/contest/2163/problem/D2

問題

隠された0～(N-1)のPermutation Pと、Q個の区間[L[i],R[i]]が与えられる。
Pにおける、どの区間に対応するmex(P[L[i]]...P[R[i]])が最大になるかを求めるinteractive問題である。

Pの区間を指定し、そのmex値を返すクエリを用いて、上記最大値を答えよ。

解法

共通部分を持たない２つの部分列に対し、少なくとも片方のmex値は0である。
というのも、P[i]=0となるiは両方に入ることがないためである。
そこで二分探索を行う。

まず入力の区間に対し、包含関係にある区間の対に対しては、小さい方の区間は無視してよい。
あとは、区間をL[i]順にソートし、前半分の全区間を含むクエリと、後ろ半分の全区間を含むクエリを行い、1以上を返す区間群を残していこう。

int T,N,Q;
int R[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>Q;
		FOR(i,N) R[i]=-1;
		FOR(i,Q) {
			cin>>x>>y;
			R[x-1]=max(R[x-1],y);
		}
		vector<pair<int,int>> V;
		FOR(i,N) if(R[i]!=-1) {
			if(V.size()&&R[i]<V.back().second) continue;
			V.push_back({i,R[i]});
		}
		int ret=-1;
		while(V.size()>1) {
			x=V.size()/2;
			int AL=V[0].first;
			int AR=V[x-1].second;
			int BL=V[x].first;
			int BR=V.back().second;
			int L,R;
			cout<<"? "<<AL+1<<" "<<AR<<endl;
			cin>>L;
			cout<<"? "<<BL+1<<" "<<BR<<endl;
			cin>>R;
			if(L==R) {
				ret=L;
				break;
			}
			vector<pair<int,int>> W;
			if(L<R) {
				for(i=x;i<V.size();i++) W.push_back(V[i]);
			}
			else {
				FOR(i,x) W.push_back(V[i]);
			}
			V=W;
		}
		if(ret==-1) {
			cout<<"? "<<V[0].first+1<<" "<<V[0].second<<endl;
			cin>>ret;
		}
		cout<<"! "<<ret<<endl;
		
	}
}

まとめ

シンプルな問題設定で良かったね。