#P9636. 构造回文串

    ID: 6100 传统题 2000ms 888MiB 尝试: 4 已通过: 3 难度: 8 上传者: 标签>CF2400提高+/省选-Manacher普通并查集顶点着色mex 计算时间戳避免清空数组序列构造

构造回文串

题面翻译

给定一个长为 NN 的整数序列 AA 满足 0≤Ai≤min⁡{i−1,N−i}0 \le A_i \le \min\{i-1,N-i\},你需要构造出 字典序最小 的 正整数 序列 SS 满足以下条件,或报告无解:

  1. ∀1≤i≤n\forall 1 \le i \le n,序列 (Si−Ai,Si−Ai+1,...,Si+Ai)(S_{i-A_i},S_{i-A_i+1},...,S_{i+A_i}) 为回文串。

  2. ∀1≤i≤n\forall 1 \le i \le n,若 2≤i−Ai≤i+Ai≤n−12 \le i-A_i \le i+A_i \le n-1,则序列 (Si−Ai−1,Si−Ai,...,Si+Ai+1)(S_{i-A_i-1},S_{i-A_i},...,S_{i+A_i+1}) 非回文串。

即 AiA_i 为以位置 ii 为中心的极长回文子串的半径。

输入格式

第一行给出数字N

第二行给出N个数字

输出格式

如题

样例 #1

样例输入 #1

7
0 0 2 0 2 0 0

样例输出 #1

Yes
1 1 2 1 1 1 2

样例 #2

样例输入 #2

7
0 1 2 3 2 1 0

样例输出 #2

Yes
1 1 1 1 1 1 1

样例 #3

样例输入 #3

7
0 1 2 0 2 1 0

样例输出 #3

No

提示

制約

  • 1 ≤ N ≤ 2 × 105 1\ \leq\ N\ \leq\ 2\ \times\ 10^5
  • 0 ≤ Ai ≤ min⁡{i−1,N−i} 0\ \leq\ A_i\ \leq\ \min\{i-1,N-i\}