#P6342. 变换问题
变换问题
题目描述
给定一个长度为 的环形数组 ,其中 ,。
一次操作可以选择任意下标 ,把 改为 或 ,其余元素不变。
对于每个 ,求把整个数组都变成 所需的最少操作次数。各目标独立地从初始数组开始计算。若无法变成 ,对应答案为 。
输入格式
第一行两个整数 。第二行 个整数 。
输出格式
一行 个整数,依次表示 的答案。
样例
7 5
2 5 1 1 2 3 2
5 5 7 -1 6
数据范围
,。
- 对于 的数据,。
- 对于 的数据,。
- 对于 的数据,。
给定一个长度为 n 的环形数组 a1,…,an,其中 a0=an,an+1=a1。
一次操作可以选择任意下标 i,把 ai 改为 max(ai−1,ai,ai+1) 或 min(ai−1,ai,ai+1),其余元素不变。
对于每个 k=1,2,…,m,求把整个数组都变成 k 所需的最少操作次数。各目标独立地从初始数组开始计算。若无法变成 k,对应答案为 −1。
第一行两个整数 n,m。第二行 n 个整数 a1,…,an。
一行 m 个整数,依次表示 k=1,2,…,m 的答案。
7 5
2 5 1 1 2 3 2
5 5 7 -1 6
3≤n,m≤2×105,1≤ai≤m。