Chlience

【题解】LUOGU 5156 [USACO18DEC]Sort It Out
没有看出来这哪里像个黑题了...Problem给出一个 $1-n$ 的排列,求最短的字典序第 $k$ 小子序列使得...
扫描右侧二维码阅读全文
27
2019/01

【题解】LUOGU 5156 [USACO18DEC]Sort It Out

没有看出来这哪里像个黑题了...

Problem

给出一个 $1-n$ 的排列,求最短的字典序第 $k$ 小子序列使得剩下的元素单调递增

Thought

很容易的就能求出使得剩下元素单调递增的子集,设其为 $s$
那么剩下的 $n-|s|$ 个元素组成的单调递增子序列必然是字典序第 $k$ 大的

考虑每个位置的转移,每次计算以当前节点为起点的 $LIS$ 有多长,以及有多少个
有两种办法实现:

第一种比较 naive
开 $n$ 个树状数组,第 $i$ 个维护长度为 $i$ 的 $LIS$,然后先计算出最长 $LIS$ 是多少再在对应的树状数组里面查即可

第二种比较正常
树状数组节点同时维护长度和个数,合并时优先考虑长度即可

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100010;
const ll inf = 1000000000000000000ll;
ll read() {
    ll ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
struct P {
    int len;
    ll way;
    void operator += (const P a) {
        if(a.len < len) return;
        else if(a.len == len) {
            way += a.way;
            if(way > inf)
                way = inf;
        }
        else {
            len = a.len;
            way = a.way;
        }
    }
};
P bit[N];
int n, a[N], maxlen;
ll ways[N], k;
bool use[N];
vector <int> lenth[N];
int lowbit(int x) {return x & (- x);}
P query(int pos) {
    P ans = {0, 0};
    for(; pos <= n + 1; pos += lowbit(pos))
        ans += bit[pos];
    return ans;
}
void add(int pos, P x) {
    for(; pos; pos -= lowbit(pos))
        bit[pos] += x;
}
int main() {
    #ifndef ONLINE_JUDGE
        freopen("in", "r", stdin);
    #endif
    n = read();  k = read();
    for(int i = 1; i <= n; ++ i)
        a[i] = read();
    add(n + 1, {0, 1});
    for(int i = n; i >= 1; -- i) {
        P q = query(a[i]);
        q.len += 1;
        add(a[i], q);
        lenth[q.len].push_back(i);
        ways[i] = q.way;
        maxlen = max(maxlen, q.len);
    }
    printf("%d\n", n - maxlen);
    int last = 0;
    for(int i = maxlen; i; -- i) {
        for(auto j = lenth[i].rbegin(); j != lenth[i].rend(); ++ j) {
            if(*j < last) continue;
            if(ways[*j] < k)
                k -= ways[*j];
            else {
                use[a[*j]] = 1;
                last = *j;
                break;
            }
        }
    }
    for(int i = 1; i <= n; ++ i)
        if(!use[i])
            printf("%d\n", i);
    return 0;
}
Last modification:January 27th, 2019 at 09:31 pm

Leave a Comment