[USACO18DEC]Sort It Out P 题解

LIS 计数

Statement

[USACO18DEC]Sort It Out P - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

Solution

其实这道题最精髓的一步在于转化题目

我们发现题目中”按顺序排好“这个操作正向模拟非常困难，我们需要寻找更简洁的充要条件

我们直接去看终态，因为终态需要是有序的，我们不妨直接把这个操作理解为把数字 \(i\) ，放到 \(i\) 号位置

那么这样，判定就变成了选择一个集合，使得集合中的数字放到应该放的位置，形成的序列是否升序

正确性：”按顺序排好“在左边比她小，右边比她大的时候停止，如若集合外的数都在应该在的位置，那么当然会在应该放的位置停止

如若存在有一些数的顺序混乱，显然我的排序操作不会影响他们的相对顺序，所以 GG

也就是说，原来条件中成立的现在条件中也成立，原来条件中不成立的现在也不成立，所以是充要的

容易想到集合外的数应该构成上升子序列，求字典序第 \(k\) 小的满足题意的集合，就是求序列中字典序 第 \(k\) 大的最长上升子序列

沿用普通序列 \(k\) 大的求法，我们应当求出从每一个数开始的 LIS 个数

Luogu 题解区的大佬采用了更为优雅的 DP 方式，即记 \(f[i]\) 表示以值 \(i\) 为开头的 LIS ，然后重定义了一下加法，算出方案数

蒟蒻比较蠢，设 \(f[i]\) 表示以第 \(i\) 个位置为开头的 LIS ，容易用 BIT \(O(n\log n)\) 求出 \(f\)

然后考虑 \(g[i]\) 表示以第 \(i\) 个位置为开头的 LIS 的方案数怎么算（没有想到可以重定义加法/kk）

枚举 LIS 长度，有这样的式子

有点吓人，不妨把 \(f[i]\) 相同的丢到同一个 vector 里面去，同一个 vector 里面下标单调递增

计算 \(vec[i]\) 时，可以二分出要查询的位置挂在 \(vec[i-1]\) 中处理 \(j>i\) 的条件，然后 BIT 处理 \(a[j]>a[i]\) 的条件

这样算出来还是 \(O(n\log n)\) ，容易发现本质和重定义加法然后和 \(f\) 一起算出来的效果相同

开始处理询问，应当从 LIS 大的开始

因为字典序的要求是对 \(a\) 的要求，所以我们把 vec 按 \(a\) 从小到大排序

那么，当我选择了 \(a[i]\) 后，下一个数 \(a[j]\) 应满足 \(j>i,a[j]>a[i]\) ，用两个变量限制一下就可以了

总复杂度 \(O(n\log n)\)

Code

#include
#define lowbit(x) (-x&x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 1e5+5;

char buf[1<<23],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
ll read(){
    ll s=0,w=1; char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
    while(isdigit(ch))s=s*10+(ch^48),ch=getchar();
    return s*w;
}

struct BITmx{
    int c[N];
    void add(int x,int v){for(;xvec[N],item[N];
ll g[N],k;
bool vis[N];

signed main(){
    n=read(),k=read();
    for(int i=1;i<=n;++i)
        a[i]=read(),b[a[i]]=i;
    for(int i=n;i>=1;--i)
        f[i]=mx.ask(n-a[i]+1)+1,
        mx.add(n-a[i]+1,f[i]),m=max(m,f[i]);
    for(int i=1;i<=n;++i)
        vec[f[i]].push_back(i);
    // for(int i=1;i<=m;++i,puts(""))
        // for(auto v:vec[i])cout<lim1&&a[vec[i][j]]>lim2){
                if(g[vec[i][j]]