#P18879. [2026多校联测]中庸数
[2026多校联测]中庸数
中庸数
题目背景
仙尊发现在三个数字中,第二大的数吸收了天地混元之气,而另外两个数字为灵珠和魔丸。
题目描述
仙尊给你一个长度为 的序列 ,然后进行 次询问,每次给出一个目标数字 ,你需要进行如下操作若干次,使得序列 的 个元素都为 。
- 选择三个连续数字 ,满足其中至少有一个数字为 。
- 修改 $a_{i-1}=a_i=a_{i+1}=\text{median}(a_{i-1},a_i,a_{i+1})$。
其中 表示 三个数字的中位数。
输入格式
第一行一个整数 ,为数据组数。
对于每组数据:
第一行两个正整数 ,表示序列长度和询问次数。
第二行 个正整数 。
接下来 行,每行一个整数 ,表示一次询问,询问目标数字为 。
输出格式
对于每组数据中的每次询问,输出一行一个整数,表示将所有数字都变为 所需要使用的最少操作次数。
如果无论如何都无法将所有数都变为 ,输出 -1。
输入输出样例 #1
2
6 2
1 10 1 10 5 4
4
1
8 2
10 10 7 4 6 10 8 7
10
6
-1
4
5
6
说明/提示
数据规模与约定
| 测试点编号 | 特殊性质 | ||
|---|---|---|---|
| 无 | |||
| 无 | |||
| 无 |
特殊性质 :。
特殊性质 :初始 序列中所有数字都互不相同。
对于所有测试点保证 $3 \leq n \leq 2 \times 10^5, 1 \leq q \leq 2 \times 10^5,\sum n \leq 10^6, \sum q \leq 10^6,1 \leq a_i \leq 2 \times 10^5,1\leq k \leq 2\times 10^5$。