账可以晚还，合同不能抄错

西岸有座海关。海关最忙的时辰，往往没有船。

船还在雾里，命令已经到了。国王喜欢临时改规矩，今天允许带三把伞，明天允许带五把，后天又给所有伞加一根柄。

抄写员若逐张改通行证，天亮前只能改完自己的名字。

老关长想了个偷懒办法。他把新命令封进不同颜色的信封，挂在各个柜台后面。

通行证先照旧放着，客人来办事，才把经过的信封一只只拆开。

办法运行得很好。直到某天来了两道命令。

第一道命令让所有伞变成原来的五倍长。第二道命令给每把伞再加三寸。

学徒把信封摞在一起，封口朝外，谁也看不出先后。

一位船长拿出旧伞试验。先拆蓝信封，后拆红信封，伞长刚好合规。

顺序倒过来，伞长多出十二寸。同一把伞，足够戳穿海关的屋顶。

屋顶漏水的时候，东岸海关送来一套新表格。

两边的栏目看起来差不多。东岸把“船数、命令数、校准常数”写在一行，西岸把最后一项另起一页。

学徒照抄旧流程，第一行就把命令数读成了海风。

老关长把两张表压在砚台下面。潮水退了一寸，又涨回来。

他这才发现，柜台真正保管着两种东西：已经兑现的结果，以及尚未拆封的变化。

前者随时要能回答，后者可以晚点落地。至于一张表来自哪座海关，属于另一份约定。

多年以后，海关把这种做法编进教材。名字很难听，像一棵专门收留迟到命令的树。

简化题面

┌─ [P2023] [AHOI2009] 维护序列
├─ 平台: 洛谷
├─ 题意: 维护数列，支持区间乘、区间加、区间求和，结果均对 P 取模。
├─ 输入: 第一行 n、P；第二行初始序列；随后给出 m 次操作。
├─ 输出: 每次区间求和操作的结果。
├─ 数据范围: n、m <= 1e5。
├─ 迁移题: P3373 首行改为 n、q、m，操作含义相同。
└─ 完整题面: https://www.luogu.com.cn/problem/P2023；https://www.luogu.com.cn/problem/P3373

代码里，命令也可以晚一点落地

线段树节点保存一段序列的和。节点上的 lazy 保存已经算进当前和、还没交给子节点的变换。

父节点的和必须随时可回答。子节点可以暂时保留旧结果。

查询或部分修改碰到分界线，down 把延期变换交给两个孩子；修改回到上层，up 用孩子的结果重算父节点。

void apply(int p, int l, int r, long long mul, long long add) {
    tree[p] = (tree[p] * mul + add * (r - l + 1)) % MOD;
    tagMul[p] = tagMul[p] * mul % MOD;
    tagAdd[p] = (tagAdd[p] * mul + add) % MOD;
}

最后一行不能凭手感写。旧变换记作 g(x)=mc*x+ac，新变换记作 f(x)=mp*x+ap，先后顺序展开为：

f(g(x)) = (mc*mp)x + (ac*mp+ap)

新乘法会碰到旧加法。单位变换是 (1,0)。

把乘法标记填成 0，整段数据都会被当成黑玻璃。

查询下钻会改变标记的存放位置，逻辑上的序列值保持不变。

父节点已经把延期变化算进总和，孩子只是收到同一份变化；查询返回后无需额外 up。部分修改真正改变了孩子，才需要重算父节点。

小模数让错误提前靠岸

大模数很宽容。少取一次模，错误可以在海上漂很久。

把模数压到 21。初值故意放大。

每次操作同时喂给线段树和一份朴素数组，build、up、query 的取模边界会很快露出来。

当树上状态始终满足“已经取模的区间和”这条合同，输出只负责读数。对拍程序负责把违规行为拖到岸上。

灯塔重新开门时，阿九把北海的纸和东海的纸分开存放。镜片仍旧一片一片地亮，塔门上的规章继续晚一点执行。

海水退去。有人来问那一小段光线的亮度。

阿九先看树上的那张纸，再去看镜片。

发布信息草案

• 标题：账可以晚还，合同不能抄错
• 摘要：双懒标记的关键是把延期操作看成函数，并在模板迁移时同时核对输入合同与状态合同。
• 标签：线段树、懒标记、仿射变换、模板迁移、对拍