#P10391. [2021年联测]挖掘机技术哪家强

    ID: 9509 传统题 2000ms 256MiB 尝试: 10 已通过: 1 难度: 9 上传者: 标签>CF2800省选/NOI-Dilworth 定理二分图建模补图排序贪心Kuhn 算法普通并查集有序集合

[2021年联测]挖掘机技术哪家强

题目描述

有 nn 台挖掘机排成一列。初始时从左到右的编号依次为 1,2,…,n1,2,\ldots,n。

每次操作给出一个位置 xx,当前位于第 xx 个位置和第 x+1x+1 个位置的两台挖掘机碰一次铲斗,然后交换位置。

执行 mm 次操作后,最多可以选出多少台挖掘机,使选出的任意两台都至少碰过一次铲斗?

输入格式

第一行两个整数 n,mn,m。接下来 mm 行,每行一个整数 xx,表示该次操作的位置。

原题文件名为 excavator.in 和 excavator.out。

输出格式

一行一个整数,表示最多可选出的挖掘机数量。

样例

6 12
1
3
5
1
2
3
5
4
3
2
4
4
4

原赛样例 2、3 见下发文件。

数据范围

  • 对于 20%20\% 的数据,n,m≤20n,m\le20。
  • 对于 60%60\% 的数据,n≤800n\le800,m≤2000m\le2000。
  • 对于所有数据,1≤n,m≤2000001\le n,m\le200000,1≤x<n1\le x<n。

原 PDF 题面