题解 P5156 【[USACO18DEC]Sort It Out】

· · 题解

屠龙宝刀,点击就送,一刀999

Problem

题意概要：给定一个长为n的排列，可以选择一个集合S使这个集合内部元素排到自己在整个序列中应该在的位置（即对于集合S内的每一个元素i，使其排到第i号位置，使得整个排列在排序后为上升序列。求满足这样条件的，且集合大小最小的集合中字典序第k小的集合（可能总结不到位，看原题面吧）

n\leq 10^5

Solution

不难发现出题人费尽心思写的题面就是在强烈暗示选取一个集合等价于将这个集合内所有元素排到自己该处于的位置（即元素i应该在位置i）

进一步发现集合内的元素很自觉的到了正确的位置，而集合外的元素不会更改相对位置，为了使最终整个排列单调递增，即要求集合外的元素必须满足在一开始就是单调递增的

求字典序第k小的满足题意的集合，取反一下，就是求序列中字典序第k大的最长上升子序列

（至此题目模型转化完成）

现在目标为求字典序第k大的最长上升子序列

在继续之前建议先将最长递增子序列的数量解决：

设置f_i表示以权值为i结尾的LIS的长度和数量，则权值x从f_1...f_{x-1}间转移，用树状数组维护前缀最大值和数量即可O(n\log n)解决

利用上面这题的思想，已经可以求得以每个元素开头的LIS长度和数量

这题和上面这题虽有不同，但本质类似，想想一般线段树求第 k 大的过程，正是依次确定每一层的节点，而为了确定每一层的节点，就需要用到所有节点子树和

同理，假设当前要求的序列的LIS长度为 t，则求第k大LIS的一个思想就是先确定第1个数，再在确定第1个数的基础上确定下一个数……以此类推可以最终确定LIS的每一位

细化一下，就是将所有可能作为LIS的第i位的数 放进第i个vector里，将每个vector内部进行元素排序，在确定每一位时从大到小确定，若当前值后面牵扯的LIS数量小于k，则将k减去这个数量然后检查下一个值，否则将这个值确定下来并开始确认下一位

（值得注意的一点，若求LIS第i层选定了位置R的元素，则接下来都不能选择R左边的元素）

Code

关于代码中的一些疑问：

#include <bits/stdc++.h>
typedef long long ll;

inline void read(int&x){
    char c11=getchar();x=0;while(!isdigit(c11))c11=getchar();
    while(isdigit(c11))x=x*10+c11-'0',c11=getchar();
}

const int N=101000;
struct Edge{int v,nxt;}e[N];
int a[N],chs[N],head[N];
int n,_;ll k;

const ll lim=1e18;

struct node{
    int v;ll c;
    inline node(){}
    friend inline void operator + (node&A,const node B){
        if(A.v<B.v)A.v=B.v,A.c=B.c;
        else if(A.v==B.v)A.c=std::min(lim,A.c+B.c);
    }
}d[N],g[N],cl;

#define lb(x) (x&(-x))

inline node qy(int x){node p=cl;for(x;x<=n+1;x+=lb(x))p+d[x];return p;}
inline void add(int x,node y){for(;x;x-=lb(x))d[x]+y;}
inline void ae(int u,int v){e[++_].v=v,e[_].nxt=head[u],head[u]=_;}

int main(){
    scanf("%d%lld",&n,&k);
    for(int i=1;i<=n;++i)read(a[i]);
    cl.c=1,add(n+1,cl),cl.c=0;
    for(int i=n;i;--i){
        g[i]=qy(a[i]);
        ++g[i].v;
        add(a[i],g[i]);
    }
    for(int i=n;i;--i)ae(g[i].v,i);
    for(int stp=qy(1).v,R=0;stp;--stp)
    for(int i=head[stp],v;i;i=e[i].nxt){
        v=e[i].v;
        if(g[v].c<k)k-=g[v].c;
        else {
            chs[a[v]]=true;
            while(R<v)g[R++]=cl;
            break;
        }
    }
    printf("%d\n",n-qy(1).v);
    for(int i=1;i<=n;++i)
        if(!chs[i])printf("%d\n",i);
    return 0;
}