问题分析

我们有一个长度为 $n$ 的序列 $a_0, a_1, \dots, a_{n-1}$，需要支持四种操作：

1. 区间加：$a_i \leftarrow a_i + c$，$i \in [l, r]$
2. 区间整除：$a_i \leftarrow \lfloor a_i / d \rfloor$，$i \in [l, r]$
3. 区间最小值查询
4. 区间和查询

其中 $n, q \leq 10^5$，需要高效算法。

---

核心难点

区间整除操作 $\lfloor a_i/d \rfloor$ 不满足线性性质，不能像加法那样直接合并标记。

如果对每个元素单独计算，最坏复杂度 $O(n)$ 会超时。

---

关键观察

1. 整除的“收敛”性质

对于固定的 $d \geq 2$，反复进行 $\lfloor x/d \rfloor$ 操作，数值会快速向 $0$ 收敛。

特别地，如果区间 $[l, r]$ 内所有 $a_i$ 都相等，那么整除后仍然全相等： $ \lfloor a_i/d \rfloor = \lfloor a_j/d \rfloor \quad \text{若 } a_i = a_j $

2. 区间极值的关系

设 $m = \min_{i \in [l,r]} a_i$，$M = \max_{i \in [l,r]} a_i$。

整除后： $ m' = \lfloor m/d \rfloor, \quad M' = \lfloor M/d \rfloor $

如果 $m' = M'$，则整个区间在整除后值相同。

---

算法设计：线段树 + 懒标记

线段树节点信息

每个节点维护：

• $\text{min}$：区间最小值
• $\text{max}$：区间最大值
• $\text{sum}$：区间和
• $\text{add}$：区间加的懒标记
• $\text{assign}$：区间赋值的懒标记（用于整除后全相等的情况）

---

操作处理

1. 区间加

与标准线段树相同：

• 更新 $\text{min}, \text{max}, \text{sum}$
• 打上 $\text{add}$ 标记

2. 区间整除

对于节点 $[L,R]$ 和查询 $[l,r]$：

1. 如果 $[L,R] \subseteq [l,r]$：

   • 计算 $m' = \lfloor \text{min}/d \rfloor$，$M' = \lfloor \text{max}/d \rfloor$
   • 如果 $m' = M'$：
     • 将整个区间赋值为 $m'$
     • 更新 $\text{min} = \text{max} = m'$，$\text{sum} = m' \times (R-L+1)$
     • 打上 $\text{assign}$ 标记，清空 $\text{add}$ 标记
     • 剪枝返回
   • 否则继续递归

2. 否则：

   • 下放标记到子节点
   • 递归处理左右子树
   • 更新当前节点的 $\text{min}, \text{max}, \text{sum}$

---

复杂度分析

• 区间加：$O(\log n)$
• 区间整除：
  • 最坏 $O(n)$，但剪枝条件使得在数值相近时很快返回
  • 实践中接近 $O(\log n)$
• 查询：$O(\log n)$

---

数学性质证明

整除后全相等的条件

设区间内数值范围为 $[m, M]$。

整除后范围变为 $[\lfloor m/d \rfloor, \lfloor M/d \rfloor]$。

两者相等的充分条件： $\lfloor M/d \rfloor - \lfloor m/d \rfloor = 0$ 即： $\lfloor M/d \rfloor = \lfloor m/d \rfloor$

当 $M - m < d$ 时通常满足（非充要但实用）。

---

数值收敛速度

对于 $x \geq 0$，每次整除至少减少到 $\lfloor x/2 \rfloor$（当 $d=2$ 时）。

对于负数，向 $0$ 收敛的速度类似。

因此即使最坏情况，经过 $O(\log \max |a_i|)$ 次操作后，整个序列会趋于稳定。

---

样例演算

输入：

10 10
-5 -4 -3 -2 -1 0 1 2 3 4
1 0 4 1    # 区间[0,4]加1 → [-4,-3,-2,-1,0,...]
1 5 9 1    # 区间[5,9]加1 → [...,1,2,3,4,5]
2 0 9 3    # 区间[0,9]整除3

第一步整除3：

• 原区间值：[-4,-3,-2,-1,0,1,2,3,4,5]
• 整除后：[-2,-1,-1,-1,0,0,0,1,1,1]
• 此时区间不再全相等，但部分子区间相等

后续查询利用线段树快速计算极值与和。

---

总结

这道题通过线段树结合区间整除的收敛性质，利用极值判断实现剪枝，将看似 $O(n)$ 的整除操作优化到接近 $O(\log n)$，是线段树在非线性操作中的经典应用。