D. Iris 与相邻乘积 详细题解

题目重述

给定一个长度为 $n$ 的数组 $b$，每次询问一个子数组 $[l, r]$。
我们可以：

1. 重排子数组内的元素。
2. 将任意元素修改为 $[1, k]$ 中的任意整数。

目标：使得重排+修改后，相邻元素的乘积 $\le k$。
求最少修改次数（重排不花钱）。

---

核心思路

1. 最优重排方式

将子数组从小到大排序为 $a_1 \le a_2 \le \dots \le a_m$（$m = r-l+1$）。
结论：最优重排方式是

$$a_m, a_1, a_{m-1}, a_2, a_{m-2}, a_3, \dots$$

即最大、最小、次大、次小、……交替排列。

证明要点（见题目末尾）：

• 最大值 $a_m$ 必须放在开头。
• 最小值 $a_1$ 放在第二位最安全，因为 $a_1 \times a_m \le k$ 是必须满足的，且 $a_1$ 最小，与任何数相乘都不容易超过 $k$。
• 剩下的子问题规模减少 $2$，递归进行。

2. 重排后的约束条件

在最优重排下，相邻对是：

$$(a_m, a_1), (a_1, a_{m-1}), (a_{m-1}, a_2), (a_2, a_{m-2}), \dots $$

约束条件转化为：
对于所有 $1 \le i \le \lfloor m/2 \rfloor$，必须满足

$$a_i \times a_{m-i+1} \le k$$

因为 $a_i$ 递增，$a_{m-i+1}$ 递减，所以最紧的约束来自 $i$ 较小和较大的组合。
实际上等价于：

$$\forall x \in [1, \lfloor m/2 \rfloor], \quad a_x \times a_{m-x+1} \le k $$

---

3. 转化为计数问题

设 $m$ 为子数组长度。
对任意正整数 $v$，定义：

• $cnt_{\le v}$ = 子数组中值 $\le v$ 的元素个数。
• $cnt_{> v}$ = 子数组中值 $> v$ 的元素个数。

观察：
对于一对 $(a_i, a_{m-i+1})$，若 $a_i > t$ 且 $a_{m-i+1} > k/(t+1)$，则它们的乘积 $> k$。
因此，要满足所有约束，必须让“大数”和“大数”不能配对。

更精确地：
对每个 $i$，考虑 $a_i$ 与 $a_{m-i+1}$ 配对。
若 $a_i \le x$，则另一数必须 $\le \lfloor k/x \rfloor$，否则乘积 $> k$。

重排后，前 $\lfloor m/2 \rfloor$ 个较小数必须与后 $\lfloor m/2 \rfloor$ 个较大数一一配对且乘积 $\le k$。

---

4. 简化约束

令 $B = \lfloor \sqrt{k} \rfloor$。
对 $x = 1, 2, \dots, B$，考虑：

• 数值 $\le x$ 的元素个数 $L_x$。
• 数值 $> \lfloor k/x \rfloor$ 的元素个数 $R_x$。

因为 $x \le B$ 时 $\lfloor k/x \rfloor \ge B$，$R_x$ 有意义。

约束等价于：
对于每个 $x \in [1, B]$，

$$\min(L_x, \lfloor m/2 \rfloor) \ge \min(R_x, \lfloor m/2 \rfloor) $$

即较小的那一半中，$\le x$ 的数量必须不少于 $> \lfloor k/x \rfloor$ 的数量。

换句话说：
如果 $R_x > L_x$，那么多出来的 $R_x - L_x$ 个大数必须被修改（改成 $1$，从而进入 $L_x$ 计数）。

---

5. 最少修改次数计算

对于固定的 $x$，需要修改的次数至少为：

$$\max(0, R_x - L_x)$$

但注意我们只有 $\lfloor m/2 \rfloor$ 对，所以实际修改次数不能超过 $\lfloor m/2 \rfloor - L_x$（因为 $L_x$ 个已经满足，剩下位置需要填满）。

所以对每个 $x$，修正后的需求为：

$$\text{need}_x = \min\left( \max(0, R_x - L_x), \lfloor m/2 \rfloor - L_x \right) $$

最终答案为所有 $x$ 中最大的 $\text{need}_x$。

---

6. 离线处理与前缀和优化

对每个询问 $[l, r]$，我们需要快速计算：

• $L_x = \text{count of } b_i \le x \text{ in } [l, r]$
• $R_x = \text{count of } b_i > \lfloor k/x \rfloor \text{ in } [l, r]$

预处理：

• 对每个 $x$，建立前缀和数组 $pre_{\le x}[i]$ 表示前 $i$ 个元素中 $\le x$ 的数量。
• 同理 $pre_{> \lfloor k/x \rfloor}[i]$。

但 $x$ 从 $1$ 到 $B$，$B \approx \sqrt{k} \le 1000$，$n \le 10^5$，直接存 $B \times n$ 太大（$10^8$ 级别）。

优化：
因为 $k$ 固定，我们可以对每个 $x$ 分别扫描一次数组，同时回答所有询问。
即：

• 外层循环 $x = 1 \dots B$
• 内层计算当前 $x$ 下的两个前缀和数组（大小 $n+1$）
• 对所有询问，用 $O(1)$ 时间得到 $L_x$ 和 $R_x$，更新 $ans[q]$。

这样空间 $O(n + q)$，时间 $O(B \cdot (n + q))$。

---

7. 额外考虑 $x > B$ 的情况

当 $x > B$ 时，$\lfloor k/x \rfloor < B$，情况已经被更小的 $x' = \lfloor k/x \rfloor$ 覆盖。
因此只需 $x = 1 \dots B$。

另外，若 $\lfloor m/2 \rfloor - L_x$ 可能为负，此时 $\text{need}_x = 0$，但代码中用 $\max$ 和 $\min$ 自动处理。

---

8. 标程解析

int B = sqrt(r);  // r = k
// 第一步：处理 <= B 的元素数量不足的情况
REP(i,0,q) {
    int len = y-x+1;
    int small = sum[y+1]-sum[x];  // <=B 的个数
    ans[i] = max(0, len/2 - small);
}

// 第二步：枚举 x = 1..B
REP(x,1,B+1) {
    // 前缀和 cnt: <=x 的数量
    // 前缀和 cnt2: <= k/(x+1) 的数量
    // 注意代码中是 <= r/(i+1)
    REP(j,0,q) {
        int len = y-x+1;
        int c1 = cnt2[y+1]-cnt2[x];  // <= k/(x+1)
        int c2 = cnt[y+1]-cnt[x];    // <= x
        // 需要修改的数 = 超出部分与可用位置的最小值
        int need = min(max(0, c1 - c2), len/2 - c2);
        ans[j] = max(ans[j], need);
    }
}

关键细节：

• 代码中用 $i$ 表示 $x$，$r$ 表示 $k$。
• $c1$ 是 $> \lfloor k/(x+1) \rfloor$ 的个数吗？
  实际上是 $\le \lfloor k/(x+1) \rfloor$ 的个数，那么 $R_x = \text{len} - c1$。 但代码中直接比较 $c1$ 和 $c2$，是因为 $\min$ 和 $\max$ 的对称性简化了表达式。

---

9. 时间复杂度

• 预处理前缀和：$O(n)$
• 对每个 $x$（$O(\sqrt{k})$ 个）：遍历所有询问 $O(q)$
• 总时间：$O(\sqrt{k} \cdot (n + q))$
  当 $k \le 10^6$，$\sqrt{k} \le 1000$，$n+q \le 2\times 10^5$ 时，约 $2\times 10^8$ 次操作，常数小可过。

---

总结

1. 最优重排：最大、最小、次大、次小交替。
2. 约束转化：对每个 $x \le \sqrt{k}$，$\le x$ 的数量必须 $\ge$ $> \lfloor k/x \rfloor$ 的数量。
3. 最少修改：取所有 $x$ 中需要的最大修改数。
4. 实现：离线枚举 $x$，用前缀和快速回答每个询问。

这个题解结合了贪心重排、数论分块、离线前缀和，是 Codeforces 2006D 的典型解法。