#P11488. [2023省队模拟]嘉心糖

    ID: 10636 传统题 3000ms 512MiB 尝试: 2 已通过: 2 难度: 9 上传者: 标签>CF2800省选/NOI-Dilworth 定理二分图建模Kuhn 算法补图链表直接模拟

[2023省队模拟]嘉心糖

题目描述

向晚正在接受嘉然的考验。

首先,嘉然选出 nn 名嘉心糖排成一个序列 aa ,并依次编号为 1,2,⋯ ,n1,2,\cdots,n 。

接着,嘉然对嘉心糖们发布了 mm 条指令。每条指令都可以用一个整数 xx ( 1≤x<n1\le x < n )描述,表示让当前处于 xx 号位置和 (x+1)(x+1) 号位置的嘉心糖贴贴并交换。

例如,对排列 [5,1,4,2,3][5,1,4,2,3] 发布 x=3x=3 的指令,会将其变为 [5,1,2,4,3][5,1,2,4,3] 。

最后,嘉然希望向晚能够找到一个尽可能大的嘉心糖集合 SS ( S⊆{1,2,⋯ ,n}S\subseteq \{1,2,\cdots,n\} ),使得集合内任意两个嘉心糖都曾经贴贴过。

输入格式

第一行两个整数 n,mn,m ,分别表示排列 aa 的长度和操作的数量。

接下来 mm 行,第 ii 行包含整数 xix_i ,表示第 ii 次操作的参数。

输出格式

输出一行共一个整数,表示集合 SS 大小的最大值。

数据范围

对于 100%100\% 的数据, 2≤n≤2×1052 \le n \le 2 \times 10^5 , 1≤m≤2×1051 \le m \le 2 \times 10^5 , 1≤xi≤n−11 \le x_i \le n-1 。

各子任务的具体信息见下表:

子任务编号 nn mm
11 ≤20\le 20 ≤5×104\le 5 \times 10^4
22 ≤103\le 10^3
33 ≤5×104\le 5 \times 10^4
44 ≤2×105\le 2 \times 10^5

输入样例 1

6 6
1
1
4
5
1
4

输出样例 1

3

样例解释

交换过位置的元素对为 (1,2)(1,2) , (4,5)(4,5) , (5,6)(5,6) 和 (4,6)(4,6) 。

当 S={4,5,6}S=\{4,5,6\} 时,集合 SS 的大小取到最大值 33 。