题解：CF1630B Range and Partition

lgx57 · 2025-02-06 10:10:23 · 题解

非常妙的好题。

首先容易发现 [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 的上升子序列即可。

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;
    }
}