YunQian DS tricks

另类线段树分治

与朴素的插入删除线段树分治不同，如果我们很容易解决先修改后询问（即可能要对修改做某种整体处理），并且询问的形式可以拆开贡献（例如 $\text{sum max...}$ ，那么我们直接把修改挂在线段树的节点上，每次处理对整个区间的贡献。

线段树区间交的处理

若修改区间为 $[L,R]$ ，询问区间为 $[l,r]$ ，且 $[L,R]$ 与 $[l,r]$ 有交时贡献过去，且贡献形式可重（例： $st$ 表可维护的 $\text{max min and or gcd}$ ），那么可以使用此 $\rm trick$ 。

具体来说，我们开两棵线段树，一棵仅修改拆出来的 $\log$ 个区间，查询的时候查询问区间的 $\log$ 个区间的祖先，另一棵修改拆出区间的祖先，查拆出的区间。

一棵修改包含的区间，查询相交的区间，一棵修改相交的区间，查询包含的区间。

不难发现，这种方式能查到所有拆出的线段中与自己有祖先关系的线段树节点，而两个区间有交的充要条件就是拆出的节点中存在祖先关系。

这个 $\rm trick$ 应用极其广泛，它甚至可以扩展到上面的线段树分治中，解决时间轴区间询问。

颜色段均摊的应用

树上每次覆盖到根是可以单 $\log$ 均摊的，每条重链都会有一个前缀死掉，所以维护单调栈即可。

但是这个一般不在瓶颈上，多数时候还带一个树状数组。

很多时候覆盖问题可以利用颜色段均摊来保证在线段树上操作的是同一片区间（P10611）。
一个数组，每个元素是一个区间，区间求区间并的长度，这个可以直接扫描线 + 颜色段均摊（P7126）。

例题：

使一颗心免于哀伤 https://yundouxueyuan.com/p/YDRG005D

有 $n$ 个函数不可重集，初始都为空，有 $m$ 个函数给定，有三种操作：

区间插入函数 $i$ ，如果已经插入了则忽略。

区间删除函数 $i$ ，如果没有就忽略。

$s,l,r,x$ ，你需要从第 $s$ 个版本到当前版本中随便选一个时刻，在这个时刻的 $[l,r]$ 这些函数集合中选出使得 $f(x)$ 最大的函数。

$n,q\le 10^5$ 。

首先先来解决没有 $s$ 的限制的情况，即时间轴上单点查询。

然后再尝试忽略删除，仅有插入。

这个时候你发现当且仅当插入区间和询问 $[l,r]$ 有交才可以贡献，所以我们可以用两棵线段树完成这个过程。

可以线段树套李超树，两只 $\rm log$ 。

然后考虑删除，你发现你已经解决了先插入后询问，所以你首先可以利用颜色段均摊将所有操作变成不交的，然后利用颜色段均摊，将拆出来的区间 $\rm push$ 到时间线段树上，然后利用“另类的线段树分治”，处理每个修改对区间内所有询问的贡献。

然后就是时间轴的区间询问，再次套用区间交结构，一棵时间树上 push 少 query 多，另一边 push 多 query 少。

洛谷 P10611 故事结局

你需要维护一个大小为 $n \times m$ 的矩阵 $A$ ，初始时其所有元素均为 $0$ 。题目还给出了一个长度为 $m$ 的序列 $b$ 。

共有 $q$ 次操作，分为两种：

1 l r x v，对于 $l \le i \le r$ ，将 $A_{x,i}$ 修改为 $v$ 。

2 l r x y，查询 $\max\limits_{i=l}^r \max\limits_{j=x}^y (A_{i,j} \times b_j)$ 。

对于所有数据满足： $1 \le n,m,q \le 4 \times 10^5$ 。 $1 \le b_i \le 10^9$ 。

首先先考虑 $b=1$ 。

考虑树套树，乍一看外层单点修改内层区间修改好像很对，但是这题是覆盖而不是 $\rm cmax$ ，这就导致一个非叶子的内层树无法直接区间修改。

换思路，外层区间修改内层单点修改，但是外层区间修改无法 $\rm pushdown,pushup$ ，怎么办？

注：check 一个线段树做法有没有假掉的有力方法是两种：先做一次大修改，再做若干次小询问；先做 $n$ 次小修改，再做一次大询问。

尝试套用区间交结构，只需要外层的两个区间有交就可以贡献了。

但它还是死了，你发现还是一样的错误，在你修改所有有交的的区间的时候，你做的这个 单点修改 并不是 $\rm cmax$ ，所以实质上破坏了可重信息的条件。

考虑每行维护一个颜色段均摊，先把每个区间会切成什么样子求出来，在线段树上 $\rm push$ 的时候就直接加入细碎的小块，很显然不改变复杂度。

这样我们发现我们可以直接在一个点撤销掉加入这个点的贡献，所以我们可以用树套树的外层单点修改内层区间修改，内层每个节点套上 std::set，三只 $\log$ 。

然后你也可以套用区间交结构，每个叶子节点开一个 std::set 就可以了，两只 $\log$ ，但是空间复杂度爆炸了。

离线，zkw线段树 + 可删堆解决。

现在考虑 $b$ 这个权值，如何兼容这个权值呢？

我们来剖析一下两棵线段树：

修改相交，查询包含的这棵解决的是修改是查询子区间的问题，所以我们应该在修改的时候乘上区间 $\max b$ 。
修改包含，查询相交的这棵解决的是查询是修改子区间的问题，所以我们应该在查询的时候乘上区间 $\max b$ 。

但这里涉及一个问题，第一棵树怎么实现？

朴素的实现是定位到所有线段树节点，再对每个节点分别做祖先链修改，但是似乎多了一个 $\log$ ！

但你发现你要求的等价于每个线段树节点与修改区间的交的 $\max b$ ，你发现这与我们 $\text{query maxb}$ 的时候做的事情是一样的！！！

所以这里要先递归下去，求出 $\max b$ 之后再修改。

同理，query 的时候也要乘上区间交的 $\max b$ 。