P5156 [USACO18DEC] Sort It Out P 题解

题意

有一个长度为 \(n\) 的排列 \(a_1,a_2,\cdots,a_n\)，选出 \(\{1,2,\cdots,n\}\) 的一个子集，对这个子集中的数依次进行如下操作：

• 设当前数为 \(v\)，则若 \(a_v\) 大于 \(a_{v+1}\)（如果有的话），就交换。如果小于，则若 \(a_v<a_{v-1}\)（如果有的话），就交换。重复上述操作知道 \(a_{v-1}<a_v<a_{v+1}\) 为止。

求大小最小的能让 \(a\) 最后有序的子集中，字典序第 \(K\) 小的。

题解

首先，注意到对于一个子集进行操作等于把子集中的所有数都排到正确的位置。如果原数组最后有序，则所有子集之外的数一开始就是有序的。

则 答案为 \(n - \texttt{[the length of LIS]}\)，第 \(K\) 小字典序的答案即为第 \(K\) 大字典序的 LIS。

考虑如何求这个东西。容易用树状数组计算出 \(i\) 开始的上升子序列的最大长度和最大长度的个数，然后从前往后通过 \(K\) 依次确定每一位即可。

时间复杂度 \(\mathcal{O(n\log n)}\)，瓶颈在树状数组。

代码

#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define pb push_back
#define mpr make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
const int N=1e5+10;
int n,a[N];
ll K;
pil dp[N];
vector<int> pos[N];
bool mark[N];
pil merge(pil x,pil y){
    if(x.first!=y.first)return max(x,y);
    return make_pair(x.first,min(K,x.second+y.second));
}
struct FenwickTree{
    pil tree[N];
    void update(int x,pil v){
        while(x>0){
            tree[x]=merge(tree[x],v);
            x-=x&-x;
        }
    }
    pil query(int x){
        pil res=make_pair(-1,0LL);
        while(x<=n){
            res=merge(res,tree[x]);
            x+=x&-x;
        }
        return res;
    }
}T;
int main(){
    scanf("%d%lld",&n,&K);
    rep(i,1,n){
        scanf("%d",a+i);
    }
    T.update(n+1,make_pair(0,1LL));
    int len=0;
    per(i,n,1){
        dp[i]=T.query(a[i]);
        dp[i].first++;
        len=max(len,dp[i].first);
        T.update(a[i],dp[i]);
        pos[dp[i].first].push_back(i);
    }
    printf("%d\n",n-len);
    int cur=0;
    per(t,len,1){
        reverse(pos[t].begin(),pos[t].end());
        for(auto v:pos[t]){
            if(dp[v].second>=K){
                mark[a[v]]=1;
                while(cur+1<v){
                    cur++;
                    dp[cur]=make_pair(0,0LL);
                }
                break;
            }
            K-=dp[v].second;
        }
    }
    rep(i,1,n){
        if(!mark[i]){
            printf("%d\n",i);
        }
    }
	return 0;
}