题解

问题重述

我们有一个长度为 $n$ 的数组 $a$（初始全0），以及一个长度为 $m$ 的操作序列。
操作有两种：

• 修改操作 $(1, l, r, v)$：将区间 $[l, r]$ 全部赋值为 $v$。
• 求和操作 $(2, l, r)$：输出当前 $a_l + \dots + a_r$。

现在有 $q$ 个查询，每个查询给出 $[L, R]$，要求：

1. 将 $a$ 重置为全0。
2. 依次执行操作序列中第 $L, L+1, \dots, R$ 个操作。
3. 将所有求和操作的结果累加作为答案。

我们需要对每个查询输出这个累加和。

---

难点分析

直接模拟每个查询会达到 $O(q \cdot m \cdot n)$ 的复杂度，不可行。
必须离线处理，利用操作和查询的结构特性。

关键观察

1. 求和操作的贡献分解

设某次求和操作 $op_i$（$i \in [L,R]$）询问区间 $[l_i, r_i]$，它的答案只取决于在它之前的最后一次覆盖每个位置的修改操作。

对于位置 $p \in [l_i, r_i]$，设最后一次覆盖 $p$ 的修改操作编号为 $last(p)$（如果不存在则 $a_p = 0$），则该位置对 $op_i$ 的贡献是 $v_{last(p)}$。

因此：

$$\text{answer}(op_i) = \sum_{p=l_i}^{r_i} v_{last(p)} $$

---

2. 查询的区间性

查询 $[L,R]$ 要求我们只考虑操作 $L..R$，这意味着：

• 只有操作 $L..R$ 中的修改会影响 $last(p)$。
• 只有操作 $L..R$ 中的求和操作才计入答案。

因此，$last(p)$ 是在 $[L,R]$ 内、在 $i$ 之前的最后一次覆盖 $p$ 的修改。

---

3. 离线扫描线思路

将查询按 $R$ 排序（或按 $L$ 排序），在扫描过程中维护一个“当前操作前缀”的信息。

---

核心算法框架

第一步：转化贡献形式

考虑每个修改操作 $op_j$（类型1）对后面求和操作 $op_i$（类型2，$i > j$）的贡献。

如果修改 $op_j$ 覆盖区间 $[l_j, r_j]$，赋值为 $v_j$，那么对于 $i > j$，$op_j$ 对 $op_i$ 有贡献当且仅当：

1. $[l_j, r_j]$ 与 $[l_i, r_i]$ 相交（即修改覆盖的位置在求和区间内）。
2. 在 $j$ 和 $i$ 之间没有其他修改覆盖相同位置（即 $op_j$ 是这些位置在 $i$ 之前的最后一次修改）。

设 $next(j)$ 表示在 $j$ 之后、最早覆盖 $[l_j, r_j]$ 中任意位置的修改操作编号（若不存在则 $next(j) = m+1$）。
那么 $op_j$ 对 $op_i$ 有贡献的条件是：

$$j < i < next(j) \quad \text{且} \quad [l_j, r_j] \cap [l_i, r_i] \neq \varnothing $$

此时，$op_j$ 对 $op_i$ 的贡献是：

$$v_j \cdot |[l_j, r_j] \cap [l_i, r_i]|$$

---

第二步：查询转为二维贡献

查询 $[L,R]$ 的答案是所有满足 $L \le j < i \le R$ 的 $(j,i)$ 对（$j$ 修改，$i$ 求和）的贡献之和。

即：

$$\text{ans}(L,R) = \sum_{j=L}^{R} \sum_{i=j+1}^{R} [op_j\text{是修改}] \cdot [op_i\text{是求和}] \cdot v_j \cdot |[l_j,r_j] \cap [l_i,r_i]| \cdot [i < next(j)] $$

其中 $[P]$ 是指示函数（$P$ 真时为1，否则为0）。

---

第三步：离线处理技巧

将查询按 $R$ 升序排序。我们扫描 $R = 1,2,\dots,m$，维护一个数据结构，使得当扫描到 $R$ 时，能快速回答所有 $R' = R$ 的查询（对每个 $L$ 求 $[L,R]$ 的答案）。

对于每个 $R$，我们需要计算所有 $j < R$ 的修改操作对以 $R$ 结尾的查询的贡献。

设当前扫描到 $R$（$op_R$ 可能是求和或修改）。

---

情况1：$op_R$ 是求和操作

对每个修改操作 $op_j$（$j < R$），如果 $j < R < next(j)$ 且 $[l_j,r_j] \cap [l_R,r_R] \neq \varnothing$，则 $op_j$ 对以 $R$ 为结尾、且 $L \le j$ 的查询有贡献 $v_j \cdot |[l_j,r_j] \cap [l_R,r_R]|$。

我们需要快速计算：

$$\sum_{j=1}^{R-1} [op_j\text{是修改}] \cdot [j \ge L] \cdot [R < next(j)] \cdot v_j \cdot |[l_j,r_j] \cap [l_R,r_R]| $$

对每个 $L$ 的查询，这需要区间 $[L,R-1]$ 中修改操作的贡献和。

---

情况2：$op_R$ 是修改操作

当 $op_R$ 是修改时，它会“阻断”前面一些修改的 $next$，从而影响后面的求和操作。
具体来说，对每个 $j < R$，如果 $[l_j,r_j] \cap [l_R,r_R] \neq \varnothing$，那么 $next(j)$ 应更新为 $R$（如果原来 $next(j) > R$）。

这意味着 $op_j$ 对 $i \ge R$ 的求和操作不再有贡献（因为 $i \ge next(j)$）。

---

第四步：数据结构设计

我们需要维护一个集合 $S$，包含所有“活跃”的修改操作 $j$，即满足 $next(j) > \text{当前扫描位置}$ 的修改。

对每个活跃修改 $j$，我们需要知道：

• 它的区间 $[l_j, r_j]$ 和值 $v_j$。
• 能快速计算对当前求和操作 $op_i$ 的交集长度贡献。

维护方法：

• 用线段树维护每个位置 $p$ 上活跃的修改操作信息。
• 对位置 $p$，如果有活跃修改覆盖它，我们需知道是哪个修改（因为同一位置只能被一个活跃修改覆盖，这是由 $next$ 定义保证的）。
• 实际上，对每个位置 $p$，覆盖它的最近修改操作是唯一的，我们可以在线段树上维护每个区间的“覆盖修改编号”和 $v$ 值（如果整个区间被同一个修改覆盖，则可以直接计算贡献）。

---

第五步：扫描过程

1. 将所有查询按 $R$ 分组。
2. 扫描 $i = 1 \dots m$：
   • 如果 $op_i$ 是修改 $(1,l,r,v)$：
     • 找出区间 $[l,r]$ 中所有被其他活跃修改覆盖的位置，将它们从活跃集合中移除（因为 $next(j)$ 变为 $i$）。
     • 将 $[l,r]$ 标记为被修改 $i$ 覆盖，值 $v$，加入活跃集合。
   • 如果 $op_i$ 是求和 $(2,l,r)$：
     • 查询线段树中区间 $[l,r]$ 的和（每个位置的值是覆盖它的活跃修改的 $v$ 值）。
     • 这个和就是 $op_i$ 的答案。
     • 对每个以 $i$ 为 $R$ 的查询 $[L,i]$，我们需要 $\sum_{k=L}^{i} \text{answer}(op_k)$，其中 $op_k$ 是求和操作。
     • 因此我们还需要维护一个前缀和数组，记录到当前位置 $i$ 为止所有求和操作的答案前缀和，这样对查询 $[L,i]$，答案就是 $pref[i] - pref[L-1]$（只考虑 $L..i$ 中的求和操作）。
3. 但注意：查询 $[L,R]$ 要求只执行 $L..R$ 的操作，而上述扫描是从1开始的。因此我们需要能“扣除” $1..L-1$ 操作的影响。

---

第六步：处理任意 $[L,R]$ 查询

经典技巧：将查询 $[L,R]$ 拆分为 $[1,R]$ 的答案减去 $[1,L-1]$ 的答案，再减去 $[1,L-1]$ 操作对 $[L,R]$ 中求和的“遗留影响”。

更精确地，设 $F(L,R)$ 为查询的答案。

定义 $G(R)$ 为执行操作 $1..R$ 得到的求和操作答案总和。

那么 $F(L,R) \neq G(R) - G(L-1)$，因为 $G(L-1)$ 中的修改会影响 $[L,R]$ 中的求和。

我们需要计算 $[1,L-1]$ 中的修改对 $[L,R]$ 中求和的贡献，这部分在 $G(R)$ 中但不在 $F(L,R)$ 中。

设 $H(L,R)$ 表示操作 $1..L-1$ 对操作 $L..R$ 中求和的贡献。
则：

$$F(L,R) = G(R) - G(L-1) - H(L,R)$$

问题转化为计算 $H(L,R)$。

---

第七步：计算 $H(L,R)$

$H(L,R)$ 是 $[1,L-1]$ 中的修改对 $[L,R]$ 中求和的贡献。
这要求修改 $j$ 满足：

1. $j < L$
2. $j$ 是修改操作
3. $next(j) > j$ 且在 $[L,R]$ 内（即 $next(j) \ge L$）
4. 对 $i \in [L,R]$ 且 $i$ 是求和操作，$[l_j,r_j] \cap [l_i,r_i] \neq \varnothing$

我们可以用扫描线处理：

• 对每个修改 $j$，它在 $[L,R]$ 内有效的区间是 $[L, \min(R, next(j)-1)]$。
• 对每个求和操作 $i$，它与修改 $j$ 的交集贡献为 $v_j \cdot |[l_j,r_j] \cap [l_i,r_i]|$。

这可以看作二维数点问题：修改 $j$ 在时间轴 $[L, next(j)-1]$ 有效，对空间区间 $[l_j,r_j]$ 有贡献 $v_j$；求和操作 $i$ 在时间 $i$ 查询空间区间 $[l_i,r_i]$ 的有效贡献和。

用线段树维护时间轴，每个时间点对应一个空间线段树（或树状数组），支持区间加、区间查询。但空间太大，需要进一步优化。

---

第八步：最终优化方案

注意到 $n, m, q$ 都可达 $5\times 10^5$，需要 $O((m+q)\log^2 n)$ 或更优的算法。

标准做法：

1. 用线段树维护数组 $a$，支持区间赋值（修改操作）和区间求和（求和操作）。
2. 对每个查询 $[L,R]$，我们无法在线处理，但可以离线分治（如时间分治或整体二分）。
3. 时间分治（CDQ分治）：
   • 将操作序列按时间分治。
   • 考虑跨过分治中点 $mid$ 的查询 $[L,R]$（$L \le mid < R$）。
   • 对于 $[L,R]$，操作分为 $[L,mid]$ 和 $[mid+1,R]$。
   • 左半的修改会影响右半的求和。
   • 在分治过程中，用扫描线处理左半修改对右半求和的贡献。
4. 在分治的每一层：
   • 将左半的所有修改操作提取出来。
   • 将右半的所有求和操作提取出来。
   • 计算左半修改对右半求和的贡献（这是一个二维贡献问题，可用一维数据结构解决）。

这样总复杂度 $O((m+q)\log m \log n)$，可以接受。

---

算法步骤总结

1. 读入 $n, m, q$ 和操作序列。
2. 将查询离线，准备进行时间CDQ分治。
3. 分治函数 solve(l, r) 处理操作时间在 $[l,r]$ 的查询：
   • 若 $l=r$，直接处理单点查询。
   • 令 $mid = (l+r)/2$。
   • 递归处理 $[l,mid]$ 和 $[mid+1,r]$ 的查询。
   • 处理跨中点的查询 $[L,R]$（$L \le mid < R$）： a. 提取 $[L,mid]$ 中的所有修改操作。 b. 提取 $[mid+1,R]$ 中的所有求和操作。 c. 对修改操作，计算它对后面求和操作的贡献（需考虑 $next$ 限制）。 d. 用扫描线+线段树计算贡献和。
4. 汇总答案，输出。

---

复杂度分析

• CDQ分治共 $O(\log m)$ 层。
• 每层处理所有修改和求和操作，总操作数 $O(m+q)$。
• 每层用线段树维护区间贡献，$O(\log n)$ 单次。
• 总复杂度 $O((m+q)\log m \log n)$，在 $5\times 10^5$ 规模下可行。

---

关键难点

1. $next(j)$ 的处理：需要快速找到覆盖区间相交的下一个修改。
2. 贡献的相交长度计算：需要高效计算 $|[l_j,r_j] \cap [l_i,r_i]|$。
3. 离线分治的边界处理：确保不重不漏。
4. 空间限制：需用高效数据结构，避免 $O(nm)$ 空间。

---

总结

本题是数据结构综合题，结合了区间赋值、区间求和、操作序列历史查询等多种要素。
通过离线分治将“修改对求和的影响”转化为二维数点问题，并用扫描线和线段树解决。
核心思想是将时间维度与空间维度分离，利用CDQ分治处理时间区间，用线段树处理空间区间，从而在可接受复杂度内完成所有查询。