#P6342. 变换问题

    ID: 6421 传统题 1000ms 1024MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-阈值三值化离线查询有序集合增量维护

变换问题

题目描述

给定一个长度为 nn 的环形数组 a1,…,ana_1,\ldots,a_n,其中 a0=ana_0=a_n,an+1=a1a_{n+1}=a_1。

一次操作可以选择任意下标 ii,把 aia_i 改为 max⁡(ai−1,ai,ai+1)\max(a_{i-1},a_i,a_{i+1}) 或 min⁡(ai−1,ai,ai+1)\min(a_{i-1},a_i,a_{i+1}),其余元素不变。

对于每个 k=1,2,…,mk=1,2,\ldots,m,求把整个数组都变成 kk 所需的最少操作次数。各目标独立地从初始数组开始计算。若无法变成 kk,对应答案为 −1-1。

输入格式

第一行两个整数 n,mn,m。第二行 nn 个整数 a1,…,ana_1,\ldots,a_n。

输出格式

一行 mm 个整数,依次表示 k=1,2,…,mk=1,2,\ldots,m 的答案。

样例

7 5
2 5 1 1 2 3 2
5 5 7 -1 6

数据范围

3≤n,m≤2×1053\le n,m\le2\times10^5,1≤ai≤m1\le a_i\le m。

  • 对于 10%10\% 的数据,n,m≤7n,m\le7。
  • 对于 30%30\% 的数据,n,m≤13n,m\le13。
  • 对于 60%60\% 的数据,n,m≤1000n,m\le1000。

原 PDF 题面