题目理解

我们有一个空数组，可以执行 $k$ 次操作。每次操作分为两步：

1. 在数组左端或右端添加任意一个整数
2. 如果存在相邻相同元素，则不断用它们的和替换这一对，直到没有相邻相同元素

要求判断能否通过恰好 $k$ 次操作得到给定的数组 $a$（长度为 $n$，相邻元素互不相同）。

---

核心思路

逆向思考：给定最终数组 $a$，考虑它是如何通过操作生成的。每次操作在两端添加元素，但可能触发合并，所以一次操作可能添加了多个原始元素（这些元素最终合并成了 $a$ 中的一个数）。

我们把每个 $a_i$ 看作是由一系列原始添加的元素合并而成的。关键问题：对于相邻两个最终元素 $a_i$ 和 $a_{i+1}$，它们是怎么来的？

---

关键观察

假设最终数组相邻的两个数是 $b = a_i$ 和 $c = a_{i+1}$。考虑它们在生成过程中最后一次相邻的情况。

• 如果它们是由两个不同的操作添加的，则添加时不会立即合并。
• 为了让它们最终不相邻，必须在它们之间插入其他元素（这些元素后来被合并或消失）。
• 更关键的是：添加 $c$ 时，如果直接添加 $\frac{c}{2^x}$ 多次，可能会与 $b$ 合并，因此需要特殊的添加顺序。

---

核心函数 max_op(a, b)

这个函数计算：已知当前数组左端（或右端）是 $a$，我们想在它旁边添加 $b$（最终让 $b$ 留在数组里且不与 $a$ 合并），最少需要多少步操作？

更准确地说：从 $a$ 旁边开始添加，最终得到相邻的 $a$ 和 $b$ 且不合并，最少需要的操作次数。

---

函数实现原理

设 $b$ 是我们想要添加的值。要添加 $b$，我们实际上可以逐步添加 $\frac{b}{2}, \frac{b}{4}, \dots$ 等，因为小的数字可以逐步合并成大的。

但问题是：当我们添加一些小的数字时，如果它们等于 $a$ 或者与 $a$ 形成相同相邻对，就会提前合并，破坏最终结果。

分情况讨论：

1. 如果 $b$ 是 $a$ 的奇数倍？
   实际上，更精确的判断是看 $a$ 和 $b$ 的关系。

2. 关键：避免提前合并
   假设 $b = m \cdot 2^t$，其中 $m$ 是奇数。要生成 $b$，我们可以先添加 $m$，然后不断添加 $m$ 来翻倍。
   但添加 $m$ 时，如果 $m = a$，就会与 $a$ 合并，变成 $2a$。这可能导致 $b$ 无法直接得到。

   所以必须先添加 $2a$ 作为“缓冲”，然后再添加 $b$。

---

代码实现

int max_op(int a, int b) {
    int min_part = a;
    while (min_part % 2 == 0 && min_part / 2 != b) {
        min_part /= 2;
    }
    if (min_part % 2 == 1) {
        return a / min_part;
    }
    int true_min = min_part;
    while (true_min % 2 == 0) {
        true_min /= 2;
    }
    return 1 + (a - min_part) / true_min;
}

解释：

• 我们不断将 $a$ 除以 2，直到不能再除（即找到 $a$ 的“奇数核”），但中途如果遇到 $a/2 = b$ 则停止。这一步是为了找到 $a$ 的某个因子，使得添加 $b$ 时不会立即合并。
• 如果最后得到奇数，则说明 $b$ 可以从这个奇数开始逐步添加得到，需要的操作次数是 $a / \text{min\_part}$。
• 否则，需要先添加一次 $2a$（花费 1 次操作），然后剩余的部分按照 $b$ 的奇数核逐步添加。

这个函数实际上计算的是：从 $a$ 生成相邻的 $a$ 和 $b$ 所需的最小操作数。

---

整体算法

1. 计算前缀和 pre[i]：表示从 $a_0$ 到 $a_i$，相邻元素间所需的操作数之和（即构建前 $i+1$ 个元素所需的最小操作数）。
2. 计算后缀和 suf[i]：类似地，从 $a_i$ 到 $a_{n-1}$。
3. 枚举每个 $a_i$ 作为“起始元素”，计算总操作数： $ \text{res} = \text{max\_op}(a_i, 0) + \text{pre}[i] + \text{suf}[i] $ 其中 max_op(a_i, 0) 表示从空数组开始构建 $a_i$ 所需的最小操作数（$b=0$ 表示没有左侧元素）。
4. 如果存在某个 $i$ 使得 $\text{res} \ge k$，输出 YES；否则 NO。

---

为什么 $res \ge k$ 可行？

因为我们可以浪费操作：
在添加某些数字时，可以故意先添加一个更小的数，让它立即与相邻数合并（相当于一次操作代替了两次），这样总操作数可以比最小值大。
实际上，每多一次额外操作，都可以通过拆分某次添加为两次来实现。
所以只要最小值 $\le k$，就一定可以构造出恰好 $k$ 次操作。

---

时间复杂度

• 每个 max_op 是 $O(\log A)$
• 预处理前缀、后缀：$O(n \log A)$
• 总复杂度 $O(n \log A)$，满足要求。

---

样例验证

以第一个样例 n=3, k=3, a=[2,1,4] 为例：

• 计算 pre[1] = max_op(2,1)
• 计算 suf[1] = max_op(1,4)
• 枚举起始位置，看是否 $\ge 3$。

根据输出结果是 YES，说明存在构造方法。

---

总结

这道题的核心是：

1. 逆向思考，将最终数组的每个数看作若干次添加后的合并结果。
2. 设计 max_op 函数计算相邻两个数之间所需的最少操作数。
3. 利用前缀和与后缀和，枚举起始位置，得到构建整个数组的最小操作数。
4. 由于可以浪费操作，只要最小值 $\le k$ 即可。