题目分析

我们有一个无限长的初始全0数组，对于每个区间 [A, B]，可以选择：

• 常规操作：区间 [A, B] 内所有位置 +1
• 翻转操作：区间 [A, B] 外所有位置 +1（等价于全局+1，然后区间内-1）

目标：选择操作方式使得最终数组的最大值最小。

---

核心思路

1. 问题转化

设最终数组为 f[x]，对于每个区间 [l, r]：

• 如果选择常规操作：f[x] += 1 当 x ∈ [l, r]
• 如果选择翻转操作：f[x] += 1 当 x ∉ [l, r]，即全局+1，区间内-1

设 x 为选择翻转操作的区间数量，则：

f[x] = (#常规操作覆盖x) - (#翻转操作覆盖x) + x

我们想最小化 max(f[x])。

---

2. 关键观察

令：

• a[x] = 覆盖位置 x 的区间总数
• b[x] = 覆盖位置 x 的翻转操作数量

则：

f[x] = a[x] - 2 * b[x] + x

目标：最小化 max(a[x] - 2 * b[x] + x)。

设最小化后的最大值为 M，则对于所有位置 x：

a[x] - 2 * b[x] + x ≤ M
=> b[x] ≥ (a[x] + x - M) / 2

我们需要选择哪些区间作为翻转操作，使得每个位置 x 的 b[x] 满足上述不等式。

---

3. 算法设计

3.1 贪心策略

代码中的 sol(up, t) 函数：

• up = 目标最大值 M
• t = 翻转操作数量 x

贪心过程：

1. 从左到右扫描位置
2. 维护当前已经安排的翻转操作数量
3. 对于每个位置 x，如果 a[x] - 当前翻转数*2 + t > up，则需要增加翻转操作
4. 选择右端点最远的区间作为翻转操作（这样可以覆盖更多后续位置）

3.2 二分答案

在 [0, mx] 范围内二分最小的可行 M，其中 mx = max(a[x])。

3.3 验证函数

chk(k) 检查 M = k 是否可行：

• 尝试 x = mx - k 或 x = mx - k + 1 两种情况
• 用贪心算法验证是否能用 x 次翻转操作达到最大值 ≤ k

---

4. 算法流程

1. 预处理：计算每个位置被多少区间覆盖 a[x]
2. 二分答案：在 [0, mx] 范围内找最小可行 M
3. 贪心验证：对于每个候选 M，用优先队列贪心选择翻转区间
4. 记录方案：记录哪些区间选择了翻转操作
5. 输出：最小最大值和操作序列

---

5. 复杂度分析

• 预处理：O(N)
• 二分：O(log N) 次
• 每次验证：O(N log N)（优先队列操作）
• 总复杂度：O(N log² N)

对于 N ≤ 200,000 可接受。

---

6. 样例验证

样例输入

5
10 10
6 6
1 7
2 5
2 7

处理过程

1. 计算 a[x] 数组
2. 二分找到最小最大值 M = 2
3. 贪心选择翻转操作：第4个区间选择翻转
4. 输出：

2
11110

（0表示翻转操作，1表示常规操作）

---

7. 关键优化

7.1 优先队列

使用最大堆维护候选区间，按右端点排序，确保选择的翻转操作覆盖范围最大。

7.2 差分数组

用差分数组快速计算区间覆盖数 a[x]。

7.3 二分搜索

利用单调性二分最小可行值。

---

算法标签

• 贪心算法 (Greedy Algorithm)
• 二分答案 (Binary Search on Answer)
• 优先队列 (Priority Queue)
• 差分数组 (Difference Array)

---

总结

本题通过将翻转操作的影响转化为数学表达式 f[x] = a[x] - 2*b[x] + x，然后利用贪心策略和二分答案在 O(N log² N) 时间内找到最优解。核心在于发现最优解的结构性质，并通过优先队列实现高效贪心选择。