题解：CF1630B Range and Partition

非常妙的好题。

首先容易发现

[x,y]

满足要求的必要条件是：在

[x,y]

中的数的个数比不在

[x,y]

的数的个数至少多

k

。（每个区间都至少多一个）。可以用二分找出最小的

y-x

。下面我们都假定已经求出了

x

和

y

。

然后我们需要发现一个结论：这个必要条件同时也是充分条件。

证明：我们令

b_i=\begin{cases} 1 & l \le a_i \le r \\ -1 & \text{otherwise} \end{cases}

，然后

sum_i=\displaystyle\sum_{j=1}^i b_i

。易知

sum_0=0,sum_n \ge k

，那么由离散的介值定理得必然存在

sum_j=1,2,\cdots,k

，即为长度为

k

的严格上升子序列，且可以通过调整使得最后一个元素一定为

sum_n

。那么每一段的和均

>0

，满足要求，证毕。

接下来就简单了。我们找到一个长度为

k

的严格上升子序列，最后一个元素一定为

sum_n

。这件事情很简单，只要去掉

sum_n

，把前面的小于

sum_n

的数拿出来找一个长度为

k-1

的上升子序列即可。

CPP

bool check(int x){
	for (int i=1;i+x<=n;i++){
		int j=i+x;
		int cnt=sum[j]-sum[i-1];
		int la=n-cnt;
		if (cnt-la>=k) return 1;
	}
	return 0;
}
struct node{
	int x,id;
}b[N],dp[N];
void sol(){
	cin>>n>>k;
	for (int i=1;i<=n;i++) sum[i]=0;
	for (int i=1;i<=n;i++) cin>>a[i],sum[a[i]]++;
	for (int i=1;i<=n;i++) sum[i]+=sum[i-1];
	int L=0,R=n-1,Ans=0;
	while (L<=R){
		int mid=(L+R)>>1;
		if (check(mid)) Ans=mid,R=mid-1;
		else L=mid+1;
	}// 二分找出 x 和 y
	int l=0,r=0;
	for (int i=1;i+Ans<=n;i++){
		int j=i+Ans;
		int cnt=sum[j]-sum[i-1];
		int la=n-cnt;
		if (cnt-la>=k){
			l=i,r=j;
			break;
		}
	}
	cout<<l<<' '<<r<<endl;
	for (int i=1;i<=n;i++){
		if (l<=a[i]&&a[i]<=r) sum[i]=1;
		else sum[i]=-1;
	}
	for (int i=1;i<=n;i++) sum[i]+=sum[i-1];
	int x=sum[n];
	int m=0;
	for (int i=1;i<=n;i++){
		if (sum[i]<x&&sum[i]>0) b[++m]={sum[i],i};//把前面的小于 sum[n] 的数拿出来
	}
	int cnt=0;
	for (int i=1;i<=m;i++){
		if (dp[cnt].x<b[i].x) dp[++cnt]=b[i];
		else{
			int L=0,R=cnt+1,Ans=0;
			while (L<=R){
				int mid=(L+R)>>1;
				if (dp[mid].x>=b[i].x) Ans=mid,R=mid-1;
				else L=mid+1;
			}
			if (b[i].x<dp[Ans].x) dp[Ans]=b[i];
		}
	}//求 LIS
	vector<int> ans;
	for (int i=1;i<k;i++) ans.pb(dp[i].id);
	ans.pb(n);
	int la=1;
	for (int x:ans){
		cout<<la<<' '<<x<<endl;
		la=x+1;
	}
}

题解：CF1630B Range and Partition

文章操作

相关推荐

评论

题解：CF1630B Range and Partition