1. 题意整理

有 $N$ 头奶牛，编号 $1 \dots N$，初始排列为 $p_1, p_2, \dots, p_N$。

一次操作：选择一个子集 $S$，按编号从小到大依次对 $S$ 中的牛喊叫。

喊叫一头牛 $x$ 的效果：

1. 只要它右边相邻的牛编号比它小，就交换，直到右边没有比它小的；
2. 然后只要它左边相邻的牛编号比它大，就交换，直到左边没有比它大的。

最终这头牛会处于一个位置，左边所有牛编号都比它小，右边所有牛编号都比它大（即它在最终排序序列中该在的位置）。

重复用同一个子集 $S$ 喊叫，直到整个序列升序。

要求：选一个 最小 的子集 $S$，使得能完成排序，并且在所有最小子集中，输出 字典序第 $K$ 小 的 $S$。

---

2. 关键转化

先考虑一次喊叫的实质。

假设牛 $x$ 的编号就是 $x$（在一般排列中，编号 $x$ 的牛在某个位置 $pos$，最终它应该在位置 $x$）。

喊叫牛 $x$ 时，它会一直向右交换，直到右边没有比它小的，再一直向左交换，直到左边没有比它大的。
实际上，这等价于 把牛 $x$ 直接放到它在最终排序序列中该在的位置，并且这个过程中会把它路径上的其他牛挤开，但不会改变这些其他牛的相对顺序（只是平移）。

多次喊叫同一个集合 $S$ 会怎样？
如果选择的 $S$ 包含了所有 不在自己位置 的牛，那么经过若干轮，它们最终都会归位。
但题目要求 最小子集，所以我们要找最少的牛，使得喊叫它们能让全部归位。

---

3. 观察与 LIS 的关系

考虑最终排序后的位置：牛 $i$ 应该在位置 $i$。

设原排列为 $p[1 \dots N]$，那么牛 $p[i]$ 的最终位置是 $p[i]$。

如果我们考虑值 $p[i]$ 和它的下标 $i$ 的关系，会发现：

结论（已知）：一个最小喊叫集合 $S$ 对应原排列的 最长上升子序列（LIS）的补集。

为什么？

• 不在 LIS 中的元素，需要通过喊叫来归位。
• 在 LIS 中的元素已经处于相对正确顺序，不需要喊叫它们。
• 最小喊叫集合的大小 = $N - \text{LIS长度}$。

---

验证样例

样例：

N=4, K=1
4 2 1 3

排序后应为 1 2 3 4。

原序列 4 2 1 3 的 LIS 可以是 2 3（长度 2），或者 1 3（长度 2）。

所以最小喊叫集合大小 = $4 - 2 = 2$。

---

4. 为什么是最小？

因为 LIS 中的元素已经相对有序，不需要喊叫，只需要喊叫不在 LIS 中的元素，每次喊叫一个，它会归位并帮助其他元素归位。
可以证明，如果 LIS 长度 = $L$，那么至少需要喊叫 $N-L$ 头牛。

---

5. 字典序第 K 小的最小子集

我们已知最小子集大小 $m = N - \text{LIS长度}$。

我们要在所有大小为 $m$ 的可行子集中，按元素升序列的字典序找第 $K$ 小。

---

转化为 LIS 计数问题

定义：

• $len[i]$ = 以 $i$ 结尾的 LIS 长度
• $cnt[i]$ = 以 $i$ 结尾且长度为 $len[i]$ 的 LIS 个数

那么全局 LIS 长度 $L = \max(len[i])$。

所有 LIS 的并集（即所有出现在某个 LIS 中的元素）的补集，就是所有最小喊叫集合的候选。

---

关键：最小喊叫集合 = 不在任何 LIS 中的元素集合。

但注意：可能有多个不同的 LIS，它们的元素集合不同。
我们要找的是：所有 LIS 的并集 的补集。

---

更精确地，设 $f(i)$ = 从 $i$ 开始的最长上升子序列长度（从后往前 DP），
$g(i)$ = 从 $i$ 开始且长度为 $f(i)$ 的 LIS 个数。

那么一个元素 $p[i]$ 属于 某个 LIS 当且仅当 $f(i) + len(i) - 1 = L$（这里 $len(i)$ 是以 $i$ 结尾的 LIS 长度，$f(i)$ 是以 $i$ 开头的 LIS 长度）。

---

6. 构造第 K 小的最小子集

最小子集 = 所有不在任何 LIS 中的元素。

但题目要求按元素编号升序排列的字典序第 $K$ 小。

因为最小子集大小固定，我们只需在补集中选择，但补集是固定的吗？
不，因为 LIS 可能有多个，它们的并集不同，所以补集也不同。

因此，我们要在 所有 LIS 的并集 中，选择补集字典序第 $K$ 小。

---

等价问题

设 $U = \{1,\dots,N\}$，$T$ = 所有 LIS 的并集。

我们要在 $U \setminus T$ 的所有可能情况中（因为不同 LIS 的并集不同），找大小固定为 $m$ 且字典序第 $K$ 小的。

---

实际上，已知结论（本题标准解法）：

• 先计算每个元素是否可能出现在某个 LIS 中（通过正反 DP 判断）。
• 那么所有最小喊叫集合 = 所有 LIS 的补集，且大小固定为 $m$。
• 按编号从小到大考虑每个元素，判断如果强制不选它（即把它放入喊叫集合），剩下的元素是否能组成一个 LIS 长度 = $L$，并且方案数足够 $K$。
• 如果能，就选它进喊叫集合，并调整 $K$；否则不选，并减去方案数。

---

7. 算法步骤

1. 计算 $len[i]$ 和 $cnt[i]$（正向 LIS DP，用树状数组维护最大值及方案数，方案数取 min(真实值, $K_{\max}+1$) 防止溢出）。
2. 计算 $f[i]$ 和 $g[i]$（反向 LDS DP，同样方法）。
3. 全局 LIS 长度 $L$ = $\max(len[i])$。
4. 标记每个元素 $p[i]$ 是否在某个 LIS 中：$len[i] + f[i] - 1 = L$。
5. 按编号 $1 \dots N$ 升序遍历，判断如果强制不选当前编号 $x$（即放入喊叫集合），检查剩余未决定元素中能否组成 LIS 长度 $L$，并计算方案数。
6. 根据 $K$ 和方案数决定是否选 $x$ 进喊叫集合。

---

8. 样例执行

样例：

4 2 1 3

LIS 长度 $L=2$，最小喊叫集合大小 $m=2$。

元素 1,2,3,4 中，在某个 LIS 中的有 {2,3} 或 {1,3} 等，并集是 {1,2,3}，补集是 {4} 不行，因为大小不够。
实际上要动态构造。

按升序尝试：

• 编号 1：不选它（即放入喊叫集），看剩下能否组成 LIS 长度 2，可以（{2,3}），方案数=1，K=1，选它。
• 编号 2：不选它，剩下 {3,4} 不能组成 LIS 长度 2，不选。
• 编号 3：不选它，剩下 {4} 不能组成 LIS 长度 2，不选。
• 编号 4：不选它，剩下 {1} 不能组成 LIS 长度 2，必须选它。

得到喊叫集合 {1,4}，输出。

---

9. 代码框架（C++）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
const ll INF = 1e18 + 10;

int n, p[N], pos[N];
ll K;

// 树状数组维护最大值及方案数
pair<int, ll> bit[N];
void update(int i, int len, ll cnt) {
    for (; i <= n; i += i & -i) {
        if (len > bit[i].first) bit[i] = {len, cnt};
        else if (len == bit[i].first) {
            bit[i].second = min(bit[i].second + cnt, INF);
        }
    }
}
pair<int, ll> query(int i) {
    pair<int, ll> res = {0, 0};
    for (; i; i -= i & -i) {
        if (bit[i].first > res.first) res = bit[i];
        else if (bit[i].first == res.first) {
            res.second = min(res.second + bit[i].second, INF);
        }
    }
    return res;
}

int len[N], f[N];
ll cnt[N], g[N];
bool inLIS[N];

int main() {
    cin >> n >> K;
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
        pos[p[i]] = i;
    }

    // 正向 LIS
    fill(bit, bit + n + 1, make_pair(0, 0LL));
    for (int i = 1; i <= n; i++) {
        auto pre = query(p[i] - 1);
        len[i] = pre.first + 1;
        cnt[i] = max(pre.second, 1LL);
        update(p[i], len[i], cnt[i]);
    }
    int L = 0;
    for (int i = 1; i <= n; i++) L = max(L, len[i]);

    // 反向 LIS（从后往前，找下降）
    fill(bit, bit + n + 1, make_pair(0, 0LL));
    for (int i = n; i >= 1; i--) {
        auto pre = query(n - p[i]);
        f[i] = pre.first + 1;
        g[i] = max(pre.second, 1LL);
        update(n - p[i] + 1, f[i], g[i]);
    }

    // 标记在某个 LIS 中的元素
    for (int i = 1; i <= n; i++) {
        if (len[i] + f[i] - 1 == L) {
            inLIS[p[i]] = true;
        }
    }

    // 输出最小大小
    cout << n - L << "\n";

    // 构造第 K 小喊叫集合
    // 这里需要进一步实现贪心选择过程
    // 略去详细实现，但思路如上

    return 0;
}

---

10. 总结

本题核心：

1. 最小喊叫集合大小 = $N - \text{LIS长度}$。
2. 最小喊叫集合是某个 LIS 的补集。
3. 按字典序第 $K$ 小构造时，用贪心 + 计数 DP 判断。