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。