问题分析

本题要求实现一个数据结构，支持三种操作：

区间加法：将区间 $[l, r]$ 内的每个元素加上 $c$

区间乘法：将区间 $[l, r]$ 内的每个元素乘以 $c$

单点查询：查询指定位置的元素值对 $10007$ 取模的结果

算法设计

同时处理加法和乘法操作的主要挑战在于它们之间的运算顺序和分配律问题。我们需要设计合适的懒标记系统来正确处理这两种操作。

分块算法与双标记系统

我们采用分块算法，并为每个块维护两个懒标记：

乘法标记 (mul)：表示块内元素需要乘以的值

加法标记 (add)：表示块内元素需要加上的值

关键设计：运算顺序 我们约定运算顺序为先乘后加，即每个元素的实际值为：

实际值=(原始值×mul)+add 标记更新规则 区间加法：

对于整块：直接更新加法标记 add = (add + c) % MOD

对于不完整块：下放标记后暴力更新

区间乘法：

对于整块：同时更新乘法标记和加法标记

mul = (mul * c) % MOD

add = (add * c) % MOD（因为加法部分也要被乘）

对于不完整块：下放标记后暴力更新

单点查询：

直接计算：(原始值 * mul + add) % MOD

算法复杂度分析

时间复杂度 区间加法/乘法：

最坏情况：$O(\sqrt{n})$（需要处理多个不完整块）

平均情况：$O(\sqrt{n})$

单点查询：$O(1)$（直接计算）

下放标记：$O(\text{块大小}) = O(\sqrt{n})$

空间复杂度 $O(n)$：存储数组和标记信息

关键优化点

双标记系统：

乘法标记和加法标记协同工作

明确的运算顺序：先乘后加

标记更新规则：

乘法操作时，加法标记也要相应更新

保持数学运算的一致性

懒标记技术：

整块操作只更新标记

部分操作才下放标记

取模优化：

在每一步运算后取模，防止溢出

使用 long long 类型避免中间结果溢出

代码总结

本题展示了如何通过分块算法处理复杂的区间操作。双标记系统的设计是解决同时包含加法和乘法操作的关键。通过合理的标记更新规则和运算顺序约定，我们实现了高效且正确的算法。

核心思想：

分块降低复杂度

懒标记减少不必要的更新

明确的运算顺序保证正确性

数学原理指导算法设计

这种双标记系统的思路可以扩展到其他需要处理多种区间操作的问题中。