P5156 [USACO18DEC]Sort It Out 题解&&LIS 统计 学习笔记

LIS数量统计

设f[i]代表以第i个数字为开头的LIS长度,g[i]代表方案数
转移时从后往前 f[i]=f[i+1···n]中的最大值 g[i]为最大长度的方案数的和
用树状数组维护即可，若需要维护以第i个数字为结尾的最长的LIS长度，正的做即可
（代码和下面题解和在一起了，感觉还算简单）

P5156 [USACO18DEC]Sort It Out 题解

题目中的排序方式类似于快速排序，不会改变其他数的相对位置
类似于之前模拟赛中的卡片重新插入排序类似的是，求出其最长子序列的长度，然后由n减去它即是集合大小
但本题还需要我们求出字典序第K小的集合，即求字典序第K大的LIS，但这样会给下面的操作带来麻烦（不转也可以，但我看不懂不转的代码）
将a(i)=x转化为b(x)=i 即由下标映射权值转化为权值映射下标，则字典序第K大转换为下标字典序第K大方便接下来的操作（保证vector内有序（虽然听说不转换vector内依旧有序但我不会证明））
然后我们用vector（或链表）来维护长度为 k 的LIS的开头有哪些，然后从长度k到1进行枚举
若以当前枚举到的数字为开头的LIS方案数比k小则这个数字不能选（因为选了之后就算是最大的字典序也无法达到k）若比k大则往下选。
注意：当前枚举到的数不能比之前枚举到的数还要小，需要特判
这题由于权值和下标老是转来转去，故将详细的解释放在代码的注释里（其实是我自己理解能力低下）

注意：代码中的下标和权值为了方便理解，标的是依据b的下标和权值。实际上b的下标是a的权值，b的权值是a的下标

#include<bits/stdc++.h>
using namespace std;
const long long inf=1e18;
long long read()
{
    long long tot=0,fs=1;
    char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') fs=-1,ch=getchar();
    while(ch>='0'&&ch<='9') tot=tot*10+ch-'0',ch=getchar();
    return tot*fs;     
}
long long n,m;
long long a[100009],b[100009];
long long k,c[100009];//排名和下标为x的数为开头的LIS方案数
struct gzw
{
    long long mx,cnt;//LIS长度和方案数
    inline friend void operator += (gzw &a, const gzw &b)//状态转移
    {
        if (a.mx < b.mx) a.mx = b.mx, a.cnt = b.cnt;
        else if (a.mx == b.mx) a.cnt = min(inf, a.cnt + b.cnt);
    }
}bit[100009];
vector<long long> vec[100009];//LIS长度为x的所有开头的下标
bool use[100009];//x这个下标是否在LIS中
void add(long long x,gzw y)//更新
{
    for(long long i=x;i;i-=(i&-i))
    {
        bit[i]+=y;
    }
}
gzw query(long long x)//由于是从后往前做的，应当找权值比当前大的转移
{
    gzw re={0,1ll};
    for(long long i=x;i<=n;i+=(i&-i))
    {
        re+=bit[i];
    }
    return re;
}
int main()
{
    n=read(),k=read();
    //cin>>n>>k;
    for(long long i=1;i<=n;i++)
    {
        a[i]=read();
        //cin>>a[i];
        b[i]=a[i];
    }
    for(long long i=n;i;i--)
    {
        gzw ls=query(b[i]+1);
        ls.mx++;//更新后长度+1
        vec[ls.mx].push_back(i);//加入下标 因为i是从大到小枚举故必然有序
        c[i]=ls.cnt;
        add(b[i],ls);
    }
    m=query(1).mx;//查询最长子序列长度
    long long cur=-1;
    for(long long i=m;i;i--)
    {
        for(long long ii=0;ii<vec[i].size();ii++)
        {
            long long j=vec[i][ii]; //下标
            if(b[j]<cur) continue; //权值不能比之前的小
            if(k<=c[j])//往下走
            {
                use[b[j]]=1;
                cur=b[j];
                break;
            }
            k-=c[j];//再往后面找下标更小的    
        }
    }
    printf("%lld\n",n-m);
    for(long long i=1;i<=n;i++)
    {
        if(!use[i]) printf("%lld\n",i);    //输出答案
    }
    return 0;
}

花了一下午终于弄懂了QAQ，果然题解写的越复杂的人越菜QAQ