颜色段均摊/ODT

由于时间原因，无法做大量的记叙，仅记录一些核心部分。

颜色段均摊指的是每次把一个序列的一个区间截出来（两端相交的段截断），把这个区间里所有的小段合成一个大段，总复杂度是 $\Theta((n+q)s)$ ，其中 $s$ 是处理每个段的复杂度。

证明只需势能分析：每次至多新增两个段，证毕。

ODT 是一种用来方便解决颜色段均摊的数据结构，它还在随机询问下的暴力问题中表现十分优秀，但此处不探讨。

在实际应用中一般只需一个 set<int>，存储每段的左端点编号，段信息存储在左端点上，初始加入 $0$ 和 $n+1$ 。

代码：

typedef set<int>::iterator IT;
IT spl(int l) {
    IT i=s.lower_bound(l);
    if(*i==l) return i;--i;
    //copy info of *i to l
    tim[l]=tim[*i];
    return s.ins(l).first;
}
auto upd(int l,int r,int t) {
    IT tl=spl(l),tr=spl(r+1);
    for(auto i=tl,j=next(i);i!=tr;i++,j++) //modify [*i,*j-1]
    //modify l,r
    s.erase(++tl,tr);
}

大体就这样，我觉得比别人写的简洁些。

一类套路——范围区间并

要求区间的范围并，我们对每个元素维护最后一次被覆盖的时候。

#10252. 「2019五校联考-知临1」数星星

给定一个序列，每个元素都是树上的一条链， $q$ 次询问 $[l,r]$ 路径并的权值和。

考虑扫描线，向右扫描 $r$ 的同时维护一个 $l\in[1,r]$ 的答案序列。

考虑 $r\gets r+1$ ，多了一条树链，我们在树上把这条树链拎出来，拆成 $\Theta(\log n)$ 个区间。

考虑把每个区间覆盖上这条树链这种颜色，把 $[1,r]$ 加上这个区间和。

再删掉之前覆盖的那些颜色，也就是对应的答案区间减掉区间和。

P9340 [JOISC 2023 Day3] Tourism

给定一个序列，每个元素都是树上的一个点， $q$ 次询问 $[l,r]$ 构成的虚树大小。

依然考虑扫描线，向右扫描 $r$ 的同时维护一个 $l\in[1,r]$ 的答案序列。

把虚树大小转化成“每个点到根的链的并的大小”减去“子树外（包括自己）全是白点的点的个数”，第一部分就是上题，第二部分是平凡的。

P6292 区间本质不同子串个数

就是数星星上了后缀树。

更强的结构——标记回收

我们考虑不使用 ODT，在线段树上维护这件事情。

颜色段均摊变成了线段树打标记，而每次覆盖只需支持标记下放，以及把子树内的区间全捞走，实现上我们维护每个点上是否有标记即可，初始时记得搞一个全局标记。

线段树最牛的地方是它本身的结构还可以维护别的信息。

P8969 幻梦 | Dream with Dynamic 加强版

需要支持区间 $x\to\text{popcount}(x)$ ，区间加，区间和。

$n\log n\log V$ 。

考虑第一个操作之后值域变为 $\log V$ ，不妨称满足所有数都是 $\mathcal O(\log V)+x$ 的一整段为颜色段，则操作 $1$ 就是颜色段均摊，记录每段中每种数的个数即可维护区间和。

区间加标记也可以一并处理。