题目理解

有 $n$ 个盒子，每个盒子有容量限制 $c[i]$。有 $q$ 次操作，每次操作在区间 $[l[j], r[j]]$ 上对每个盒子进行糖果的增加或减少，但受到容量上限 $c[i]$ 和下限 $0$ 的限制。

我们需要求出所有操作结束后，每个盒子中糖果的数量。

---

关键观察

1. 问题转化

每个盒子的操作是独立的，但操作是区间形式。我们可以考虑用扫描线的方法，从左到右处理每个盒子，同时维护一个数据结构来处理时间轴上的操作。

2. 操作特性分析

对于每个盒子 $i$，设它经历的操作序列对应的前缀和为 $S_j$（第 $j$ 次操作后的总变化量，不考虑容量限制）。实际糖果数量 $ans[i]$ 满足：

• $0 \leq ans[i] \leq c[i]$
• 如果整个过程中 $S_j$ 的最大值与最小值之差 $\leq c[i]$，那么 $ans[i] = S_q - \min_{j} S_j$
• 否则，需要找到最后一次"触底"或"触顶"的位置，然后计算最终结果

---

算法设计

1. 扫描线框架

我们按盒子编号从左到右扫描：

• 当盒子 $i$ 进入一个操作的区间时，将该操作加入时间轴
• 当盒子 $i$ 离开一个操作的区间时，将该操作从时间轴撤销
• 对于每个盒子 $i$，在时间轴上计算糖果数量

2. 线段树维护

我们使用线段树维护时间轴上的信息：

• 每个叶子节点表示一个时间点的前缀和 $S_j$
• 每个节点维护区间内的最小值 $t1$ 和最大值 $t2$
• 支持区间加操作（懒标记）

3. 关键计算

对于每个盒子 $i$：

情况1：极差不超过容量

如果 $t2[1] - t1[1] \leq c[i]$，说明在整个过程中糖果数量始终在容量范围内波动，则：

$$ans[i] = S_q - t1[1]$$

其中 $S_q$ 是最终的总变化量。

情况2：极差超过容量

需要找到最后一个时间点 $loc$，使得从 $loc$ 到结束的极差 $\geq c[i]$。使用二分查找：

• 在 $[1, q]$ 中二分查找最大的 $mid$，使得 $[mid, q]$ 的极差 $\geq c[i]$
• 设 $[loc, q]$ 的最小值为 $mn$，最大值为 $mx$，$loc$ 时刻的值为 $val$
• 如果 $val = mn$（最后一次触底），则 $ans[i] = c[i] + S_q - mx$
• 如果 $val = mx$（最后一次触顶），则 $ans[i] = S_q - mn$

---

算法正确性

1. 扫描线正确性

每个盒子 $i$ 只受 $l[j] \leq i \leq r[j]$ 的操作影响。通过扫描线，我们确保在处理盒子 $i$ 时，时间轴上只包含影响它的操作。

2. 极差判断的合理性

• 如果整个过程中前缀和的最大最小值之差不超过容量，说明糖果数量始终在 $[0, c[i]]$ 内，没有受到上下限的约束
• 否则，一定存在触底（$S_j$ 达到最小值）或触顶（$S_j$ 达到最大值）的时刻

3. 二分查找的正确性

二分查找找到的是最后一个极差 $\geq c[i]$ 的时间点，从这个时间点开始，后续操作使糖果在容量范围内变化，但不再同时触底和触顶。

---

复杂度分析

时间复杂度

• 扫描线部分：每个操作被加入和撤销各一次，$O(q)$
• 线段树操作：每次区间加 $O(\log q)$
• 每个盒子的二分查找：$O(\log q)$，每次查询 $O(\log q)$
• 总复杂度：$O((n+q) \log q)$

空间复杂度

• 线段树：$O(q)$
• 存储操作：$O(n+q)$
• 总空间：$O(n+q)$

---

代码实现要点

1. 数据结构

// 线段树节点
ll t1[N<<2], t2[N<<2], la[N<<2];  // 最小值、最大值、懒标记
vector<int> ad[N], de[N];          // 进入和离开操作

2. 关键函数

• pushdown(): 下传懒标记
• add(): 区间加操作
• query(): 查询区间最小最大值
• distribute_candies(): 主函数，实现扫描线逻辑

3. 扫描线流程

for i = 0 to n-1:
    // 加入以i为左端点的操作
    for op in ad[i]:
        add(op时间到结束, v[op])
    
    // 撤销以i-1为右端点的操作  
    for op in de[i]:
        add(op时间到结束, -v[op])
    
    // 计算盒子i的结果
    if 极差 <= c[i]:
        ans[i] = 总变化量 - 最小值
    else:
        二分查找loc
        if loc时刻值 == 最小值:
            ans[i] = c[i] + 总变化量 - 最大值
        else:
            ans[i] = 总变化量 - 最小值

---

算法标签

• 线段树
• 递推
• 二分
• 模拟

---

总结

本题通过扫描线将区间操作转化为对每个盒子的独立处理，利用线段树维护时间轴上的前缀和，通过分析前缀和的极差特性来确定最终糖果数量。算法巧妙地避免了直接模拟每个操作，将时间复杂度优化到可接受的范围。