题解：CF2163D2 Diadrash (Hard Version)

首先，这类题有一个经典trick，就是对于一个

[0,n-1]

排列的某个子集的

\text{mex}

等价于其补集的

\min

。证明显然。

对于此题，已知一个集合的

\text{mex}

的值，如果我们往这个集合加一个数字，这个值一定不会变小。由此可以推断原题中所有被其他询问包含的询问都是无用的。此时，区间仅剩

O(N)

个。假定剩余

m

个区间并且区间已经升序排序。

设

f_i = \min_{j=1}^{i}{p_j}

，

g_i = \min_{j=i}^{n}{p_j}

，显然

f

与

g

分别是单调递减和单调递增的。同时可以得到

mex_{i=l}^{r}{p_i}=\min(f_{l-1},g_{r+1})

。那么，对于所有询问得到的函数，一定是一个增函数和一个减函数对应位置的

\min

。如图：

红点就是最终答案所在位置，二分选哪个区间即可。

有个细节是答案有可能取在极值点两边，所以最终答案要选择极值点附近两点比较大小。

次数

2\times \log_2{n}+2

。

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
int a[N],n,q;
int ask(int l,int r){
	cout<<"? "<<l<<" "<<r<<endl;
	int ret;
	cin>>ret;return ret;
}
int l[N],r[N],m;
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);
	int T;cin>>T;
	while(T--){
		cin>>n>>q;
		for(int i=1;i<=n;i++)a[i]=i+1;
		while(q--){
			int l,r;cin>>l>>r;
			a[r]=min(a[r],l);
		}
		int mn=n+1;
		for(int i=n;i>=1;i--){
			if(a[i]>=mn)a[i]=i+1;
			else mn=min(a[i],mn);
		}
		m=0;
		for(int i=1;i<=n;i++)if(a[i]!=i+1)l[++m]=a[i],r[m]=i;//所有有用的区间
		int p=0;
		for(int i=1<<20;i;i>>=1){
			if(p+i<=m&&ask(l[p+i],n)>=ask(1,r[p+i]))p+=i;
		}
		int ans=0;
		if(p!=0)ans=max(ans,ask(l[p],r[p]));
		if(p+1<=m)ans=max(ans,ask(l[p+1],r[p+1]));
		cout<<"! "<<ans<<endl;
	}
	return 0;
}

题解：CF2163D2 Diadrash (Hard Version)

文章操作

相关推荐

评论

题解：CF2163D2 Diadrash (Hard Version)