题目大意

有一排 $n$ 块木板，你需要选择一个分界点 $k$（$1 \le k \le n-1$），使得：

• 前 $k$ 块木板涂一种颜色
• 后 $n-k$ 块木板涂另一种颜色

有 $m$ 种颜色，第 $i$ 种颜色可以涂 $a_i$ 块木板（即这种颜色的油漆量足够涂 $a_i$ 块木板）。
对于给定的 $k$，一种颜色能用于前 $k$ 块当且仅当 $a_i \ge k$，能用于后 $n-k$ 块当且仅当 $a_i \ge n-k$。

要求：对于每个 $k$，统计前 $k$ 块和后 $n-k$ 块颜色不同的方案数，并对所有 $k$ 求和。

---

解题思路

1. 固定 $k$ 时的方案数

对于固定的 $k$，定义：

• $x$ = 满足 $a_i \ge k$ 的颜色数量（可用于前 $k$ 块）
• $y$ = 满足 $a_i \ge n-k$ 的颜色数量（可用于后 $n-k$ 块）

如果不要求两段颜色不同，方案数为 $x \cdot y$（前段从 $x$ 种中选一种，后段从 $y$ 种中选一种）。

但其中包含了前后段颜色相同的情况。
前后段颜色相同时，这种颜色必须同时满足 $a_i \ge k$ 和 $a_i \ge n-k$，即 $a_i \ge \max(k, n-k)$。

设 $z$ = 满足 $a_i \ge \max(k, n-k)$ 的颜色数量，则前后段颜色相同的方案数就是 $z$（因为选定一种这样的颜色，整个栅栏全涂它，对应唯一一种分配）。

因此，对于固定的 $k$，前后段颜色不同的方案数为：

$$x \cdot y - z$$

---

2. 如何快速计算 $x, y, z$

将数组 $a$ 从小到大排序。

• $x$ = 大于等于 $k$ 的元素个数 = $m - \text{第一个} \ge k \text{的位置}$
• $y$ = 大于等于 $n-k$ 的元素个数 = $m - \text{第一个} \ge n-k \text{的位置}$
• $z$ = 大于等于 $\max(k, n-k)$ 的元素个数

注意到：

• 若 $k \ge n-k$（即 $k \ge n/2$），则 $\max(k, n-k) = k$，此时 $z = x$
• 若 $k < n-k$（即 $k < n/2$），则 $\max(k, n-k) = n-k$，此时 $z = y$

因此：

$$z = \min(x, y)$$

于是方案数简化为：

$$x \cdot y - \min(x, y)$$

---

3. 最终答案

对所有 $k = 1, 2, \dots, n-1$ 求和：

$$\text{答案} = \sum_{k=1}^{n-1} \left( x_k \cdot y_k - \min(x_k, y_k) \right) $$

其中 $x_k = m - \text{lower\_bound}(a, k)$，$y_k = m - \text{lower\_bound}(a, n-k)$。

---

4. 时间复杂度

• 排序 $a$：$O(m \log m)$
• 对于每个 $k$，两次二分查找（$O(\log m)$），共 $n-1$ 次
• 总复杂度：$O((m + n) \log m)$