思路
单次影响与维护信息
首先考虑每一种修改操作单次对信息的影响，特殊地，将统计历史信息也视作一次操作。比如，区间加，统计区间历史信息和两种操作可以表示成：
sum←sum+v⋅lenans←ans+sum
同时，我们可以知道要维护三个信息：
len,sum,ans，分别表示区间长度、区间和、区间历史信息和。
设计标记与影响信息
然后我们想象，对当前区间的所有单次操作，按顺序排在一个队列里面，比如记区间加操作为
A，统计区间历史信息和操作为
S，可能有操作队列：
我们所设计的标记，其实就是提取出上面队列的关键信息以代表整个队列。
我们先考虑这整个队列中所有
A 操作对
sum 的影响，有：
因此我们需要维护的一个标记就是所有
A 操作的权值之和。
然后考虑整个队列中所有
S 操作对
ans 的影响，有：
拆开：
ans←ans+(i∈Queue∑[typei=S])⋅sum+(i∈Queue∑[typei=S]j<i∑[typej=A]vj)⋅len
因此，我们需要维护两个标记，一个是队列中
S 操作的数量，另一个是队列中所有
S 操作的前缀
A 操作权值和，也就是每一次
S 操作当时的
A 操作权值和之和。
整理一下：
我们需要维护三个标记，令作：
taga=i∈Queue∑[typei=A]vicnts=i∈Queue∑[typei=S]tags=i∈Queue∑[typei=S]j<i∑[typej=A]vj
他们对信息的影响为（请注意，右式中的信息均为修改前的原值）：
sum←sum+len⋅tagaans←ans+cnts⋅sum+len⋅tags
队列拼接与标记下传
我们考虑标记下传的意义，实际上就是把父节点的操作序列，拼接在子节点的操作序列队尾。在后面，我们为新拼接的序列信息变量名后打上
′ 以示区分。
我们只需要根据想象中的拼接起来的队列模拟标记值的变化即可，这一步一般是简单的，比如上面的例子，有：
taga←taga+taga′cnts←cnts+cnts′tags←tags+sum⋅cnts′+tags′
对
tags 的更新相对复杂些，中间项其实就是前半部分队列的和对后半部分队列统计的前缀和产生了影响。
到这里我们就已经完成了信息维护到标记下传的所有部分的设计。
例题
- 区间加 a。
- 区间加 b。
- 维护区间历史 ∑a⋅b 和。
让我们通过上述方法开始设计。
首先，实际上有三种操作：区间加
a，区间加
b，统计历史信息。可以表示成：
然后想象一个序列：
ABSABASAABBSBAS…
为了方便，我们提前设计一下两个标记以防止后面的公式长的一批：
Ta=i∈Queue∑[typei=A]viTb=i∈Queue∑[typei=B]vi
以及口述一下，记
Sab(k) 表示进行到第
k 次操作时的
Sab 信息，
Sa(k) 表示进行到第
k 次操作时的
Sa 信息，
Sb(k) 同理。
于是有：
Sa←Sa+len⋅TaSb←Sb+len⋅TbSab←Sab+Sb⋅Ta+Sa⋅Tb+len⋅Ta⋅Tbans←ans+i∈Queue∑[typei=S]Sab(i)
我们考虑拆开
∑i∈Queue[typei=S]Sab(i)。
整理设计标记：
Ta=i∈Queue∑[typei=A]viTb=i∈Queue∑[typei=B]vicnts=i∈Queue∑[typei=S]ha=i∈Queue∑[typei=S]Sa(i)hb=i∈Queue∑[typei=S]Sb(i)hab=i∈Queue∑[typei=S]Sab(i)
整理对四种信息的影响（同理，右式内变量为原值）：
Sa←Sa+len⋅TaSb←Sb+len⋅TbSab←Sab+Sb⋅Ta+Sa⋅Tb+len⋅Ta⋅Tbans←ans+Sabcnts+haSb+hbSa+len⋅hahb
然后我们考虑合并序列、下传标记，比较简单，直接给出结果，记号同上：
Ta←Ta+Ta′Tb←Tb+Tb′cnts←cnts+cnts′ha←ha+Ta⋅cnts′+ha′hb←hb+Tb⋅cnts′+hb′hab←hab+TaTb⋅cnts′+Ta⋅hb′+Tb⋅ha′+hab′
然后就做完啦。
给出我实现的信息结构体代码：
CPPstruct node{
ull len=0,sa=0,sb=0,sab=0,ans=0,ta=0,tb=0,cq=0,ha=0,hb=0,hab=0;
inline void operator*=(node t){
ans+=sab*t.cq+t.ha*sb+t.hb*sa+t.hab*len;
sab+=t.ta*sb+t.tb*sa+t.ta*t.tb*len;
sa+=t.ta*len,sb+=t.tb*len;
cq+=t.cq;
hab+=ta*tb*t.cq+ta*t.hb+tb*t.ha+t.hab;
ha+=ta*t.cq+t.ha,hb+=tb*t.cq+t.hb;
ta+=t.ta,tb+=t.tb;
}
friend inline node operator+(node a,node b){
node c;
c.len=a.len+b.len;
c.sa=a.sa+b.sa;
c.sb=a.sb+b.sb;
c.sab=a.sab+b.sab;
c.ans=a.ans+b.ans;
return c;
}
}
P8868 [NOIP2022] 比赛