来个 flow 做法。
首先如果 \(k > \operatorname{LIS}(a)\) 则一定无解。
先来考虑 \(k = 1\) 时怎么做。
\(\operatorname{LIS}(b) = 1\) 就相当于是限制 \(b\) 必须是降序排列，于是跑出 \(a\) 的最长下降子序列，若长度 \(< m\) 则无解，否则任意选取 \(m\) 个元素即可。
这启发在 \(k\) 更大的时候，去找到 \(k\) 个不交的下降子序列，那么这 \(k\) 个子序列的并所构成的 \(\operatorname{LIS}\) 一定 \(\le k\)。
但是这个题要求 \(= k\)，那么有没有办法把 \(< k\) 的情况去掉呢？
考虑最大化子序列的总长度，这就能使子序列的 \(\operatorname{LIS} = k\)。
这是因为若子序列的 \(\operatorname{LIS} < k\)，那么根据 dilworth 定理，可以用 \(\operatorname{LIS}\) 个序列覆盖完这个序列，就还有 \(k - \operatorname{LIS}\) 的序列可以继续选，那么长度一定不为最长的。
需要注意的是正确性是建立在 \(k\le \operatorname{LIS}(a)\) 的前提下的。
并且发现这样求解后顺带也就求出了 \(k\) 对应的 \(m_\max\)，若 \(m > m_\max\) 时则无解。
否则考虑从 \(m_\max\) 的序列保留下 \(m\) 个数使得此时仍然有 \(\operatorname{LIS} = k\)。
这是简单的，因为长度为 \(m_\max\) 的序列保证了 \(\operatorname{LIS} = k\)，所以可以直接跑出该序列的一个 \(\operatorname{LIS}\)，保留下这 \(k\) 个数并在剩余的 \(m_\max - k\) 个数中随意选 \(m - k\) 个即可。
那么除了找到长度和最长的 \(k\) 个不交下降子序列以外，其他的部分都可以简单的做到 \(\mathcal{O}(n^2)\) 或者是 \(\mathcal{O}(n\log n)\)，接下来就只考虑求解子序列了。
对于这个问题并没有一个很好的贪心（？），于是考虑 flow。
考虑对每个点引入入点出点 \(in(i), out(i)\)，连边：
- \((S, S', k, 0), (S', in(i), 1, 0), (out(i), T, 1, 0)\)。
- \((in(i), out(i), 1, 1)\)。
- \((out(i), in(j), 1, 0)(i < j, a_i > a_j)\)。
跑最大费用最大流即可，跑出来后可以检查 \((in(i), out(i))\) 的流量便可知道 \(i\) 是否被选入子序列中。
此时用 Primal Dual 原始对偶和 \(\mathcal{O}(n^2)\) 朴素优化 dijkstra 便可做到 \(\mathcal{O}(n^3)\)。
对于第三类连边，是个二维偏序的形式，可以考虑线段树 / 树状数组优化建图，使点数边数都为 \(\mathcal{O}(n\log n)\) 级别。
此时 Primal Dual 原始对偶加上堆优化 dijkatra 可以做到 \(\mathcal{O}(n^2 \log^2 n)\)。
瓶颈在于最短路（此处转为了最小费用最大流），考虑到该图的边权绝对值的和为 \(n\)，于是 Primal Dual 中的最短路值域也只会是 \(\mathcal{O}(n)\) 的，那么可以直接对每个 \(dis\) 开桶维护。
这样就做到了 \(\mathcal{O}(n^2\log n)\)。
不过这样可能还是过不了，还需要进一步卡常。
考虑把每次跑一条增广路变为一次性找到该最短路的所有增广路，也就是把找增广路换为 dinic 即可。
这样的道理应该是增广路的权值和是 \(-n\)，所以只会跑 \(\mathcal{O}(\sqrt n)\) 轮的最短路（？）。
submission。