#P9504. 「SNOI2020」排列

    ID: 6081 传统题 1000ms 256MiB 尝试: 2 已通过: 2 难度: 10 上传者: 标签>CF3000省选/NOI-排列构造逆向思考有限候选集缩减DAG 动态规划树状数组扫描线路径恢复懒标记线段树一维前缀和

「SNOI2020」排列

题目描述

有一个 nn 阶排列 pp,其前 kk 位 p1,p2,…,pkp_1, p_2, \dots, p_k 已经确定了。

定义排列 pp 中,[l,r][l, r] 是一个值域连续段当且仅当:

$$\max(p_l, p_{l+1}, \dots, p_r) - \min(p_l, p_{l+1}, \dots, p_r) = r-l$$

pp 中值域连续段个数即所有 1≤l≤r≤n1\le l\le r\le n 中值域连续段的总数。

请你求出:所有可能的排列 pp 中,值域连续段个数的最大值,以及任意一种方案。

输入格式

第一行两个整数 n,kn,k,分别表示排列的阶数和以及确定的位数。

接下来一行由空格分隔的 kk 个正整数 p1,p2,…,pkp_1, p_2, \dots, p_k,表示排列已知的部分。(k=0k=0 则此行为空)

输出格式

输出第一行一个整数表示值域连续段个数的最大值。

第二行 nn 个正整数表示任意一种方案。

4 1
2
8
2 1 3 4

数据范围与提示

对于所有数据,1≤n≤2×105,0≤k≤n1\le n\le 2\times 10^5, 0\le k\le n。

  • 对于 10%10\% 的数据,n≤10n\le 10;
  • 对于另外 20%20\% 的数据,n≤22n\le 22;
  • 对于另外 10%10\% 的数据,k≤1k\le 1;
  • 对于另外 20%20\% 的数据,k=nk = n;
  • 对于余下 40%40\% 的数据,无特殊限制。