P7931 [COCI 2021/2022 #1] Volontiranje
题目描述
给定一个 $1\sim n$ 的排列 $p$,请从这里面取出尽可能多的不交的上升子序列,且他们的长度为原排列的 LIS 的长度,并构造一组方案。
输入格式
无
输出格式
无
说明/提示
#### 数据范围
对于全部数据,$1\le n\le 10^6$,$1\le p_i\le n$。
| Subtask | 数据范围 | 分值 |
| :-----: | :---------: | :--: |
| $1$ | $n\le 15$ | $10$ |
| $2$ | $n\le 10^3$ | $40$ |
| $3$ | 无特殊限制 | $60$ |
#### 说明
**本题总分 $110$ 分。**
本题译自 [Croatian Open Competition in Informatics 2021/2022](https://hsin.hr/coci/archive/2021_2022) [Contest #1](https://hsin.hr/coci/archive/2021_2022/contest1_tasks.pdf) T5 Volontiranje。
在附加文件中下发了一份 checker.cpp。