由记得上一次吃屎还是上一次。

Ynoi Easy Round 2016 镜中的昆虫

先考虑不带修改的问题怎么做，设 $pre_i$ 表示上一个为 $i$ 的元素出现的位置，没有出现过设置为 $0$。

那么现在我们需要统计的就是 $pre_i< l$ 且 $i\in [l,r]$ 的数量，注意到是一个二位偏序那么就写一个树状数组统计就行了。

那么待修之后怎么做呢，添加时间这个第三维之后就只有写 cdq 分治做了。

CDQ 分治解决这类问题的算法流程如下：

1. 找到这个序列的中点 $mid$。
2. 将 $[l,mid]$ 和 $[mid+1,r]$ 的部分分开递归处理。
3. 解决 $[l,mid]$ 和 $[mid+1,r]$ 之间的贡献。

考虑一下 CDQ 怎么解决三维偏序，首先把第一维进行排序然后开始分治。

因为所有的 $[l,mid]$ 的 $a_i$ 都比 $[mid+1,r]$ 的 $a_i$ 小，所以可以直接按照 $b_i$ 排序然后把 $c_i$ 作为下表丢到树状数组里面求前缀和就行了。

回到这个问题，因为有单点修改所以需要修改 $pre_i$，那么我们不妨添加一维表示时间，只有时间小的才能对时间大的造成影响。

对于修改操作，我们有 $(time,pos,pre,val)$ 表示在 $time$ 时间把 $pos$ 位置的 $pre$ 的值增加 $val$。

对于询问操作，设 $(time,l,r,ans)$ 表示在 $time$ 的时间询问 $[l,r]$ 的答案。

于是我们就解决了单点修改的问题，时间复杂度为 $O(n\log^2n)$。

对于区间的玩意，考虑写颜色段均摊（也就是珂朵莉树），容易理解 $pre_i$ 被修改的数量是 $O(n+m)$ 的。

split 是珂朵莉树的核心操作，选择一个位置 $x$，然后将原本包含 $x$ 的区间 $[l,r]$ 分裂成 $[l,x-1]$ 和 $[x,r]$。

assign 操作的意义是将 $[l,r]$ 这一段赋值成 $v$，具体的把两个端点 split 出来然后把中间的迭代器 erase 掉最后再添加一个迭代器 $(l,r,v)$。

具体的把中间的迭代器拿出来然后全部改掉就行了，特别的我们不知道最前面的 $pre$ 的值是什么，所以我们需要给每一种颜色开一个 set 在里面存这个颜色都有哪些块以快速的找到。

CF1464F My Beautiful Madness

这个题目最困难的部分在于读懂题目。

题目给定了一棵树，然后再在树上选择了一些路径。

假设 $x$ 是所有路径的 $lca$ 中的最深的节点 $z$ 向上跳 $d$ 步的位置，那么如果有交集 $x$ 就一定会被包含。

假设 $x$ 向上跳 $d$ 步到大的点是 $y$，那么如果有路径不在以 $y$ 为根的子树内，那么这个路径一定是不合法的。因为在 $z$ 为根的子树内距离 $x$ 的路径都可以到达，所以我们不需要考虑 $lca$ 在 $z$ 子树内的情况。

如果一个路径有节点在 $y$ 的子树但是 $lca$ 不在，那么这个路径显然会经过 $y$，所以一定合法。

只需要考虑 $lca$ 在 $y$ 的子树里有不在 $z$ 的子树的情况就可以了。

考虑将每一个路径的 $lca$ 放到线段树里维护 $dfn$ 区间里的直径，直接判断直径的两个端点的距 $x$ 的距离是否比 $d$ 大就可以了。

P6792 SNOI2020 区间和

如果只有操作 $0$ 或者操作 $1$，那么这个问题是容易解决的。

如果有操作 $0$，那么直接写吉司机线段树就行了，而如果只有后面的东西就是很板的线段树合并题目。

为了防止我忘记怎么写吉司机，如果 $mn\ge x$ 那么无意义返回，如果 $mn<x<se$ 那么 $mn=x$ 然后返回，对于其他情况继续递归就对了。

考虑怎么为 $mn<x<se$ 的时候维护这个经典的线段树合并的信息。

对于这个经典的线段树合并操作，我们需要维护包含左端点的最大和 $lmx$，包含右端点的最大和 $rmx$，最后是这个节点的贡献 $ans$。

那么要计算 $ans$ 有公式：

$ans(rt)=\max\{ans(ls),ans(rs),rmx(ls)+lmx(rs)\}$

所以我们需要快速的确定其儿子的 $lmx$ 和 $rmx$ 值才能打懒惰标记，因为 $lmx$ 和 $rmx$ 具有对称性所以下面只考虑 $lmx$ 操作。

如果 $lmx$ 和 $ans$ 的区间没有不改变，那么区间 $\max$ 的影响是容易计算计算的。

我们只需要记录这个区间中有多少最小值就可以快速计算了，自然的想到考虑什么时候其区间不会改变。

考虑下面一个情况，假设现在 $lmx$ 的区间的紫色，容易理解经过区间 $\max$ 操作是永远不可能取到橙色区间的，因为给橙色区间造成的贡献也会反应到紫色区间身上，然而本来选择的区间的紫色的，所以紫色拥有而橙色不拥有的区间肯定是答案造成了正面贡献的。

进一步的，我们得到了右端点经过 $\max$ 操作只会增加，于是总共的增加次数最大只有 $O(n\log n)$，这是一个很优秀的性质。

需要注意即使修改操作并没有包含整个区间因为其只会增加区间和所以 $lmx$ 的右端点依然不会向左，这是容易理解的。

假设紫色区间和红色区间的和为分别为 $S_1$ 和 $S_2$，其中包含的最小值个数分别为 $M_1$ 和 $M_2$，那么红色区间的想要超过紫色区间所受到的区间 $\max$ 的值 $V$ 和原本的最大值 $mx$ 的差 $\Delta$，也就是 $V-mx$ 应该满足：

$\Delta\ge \dfrac{S_1-S_2}{M_2-M_1}$

需要注意如果 $M_1=M_2$，那么红色区间永远都不可能超过紫色区间。

那么我们可以维护区间中阈值的最小值，然后将 $\Delta$ 进行累加，当 $\Delta$ 超过这个阈值时就进行类似于吉司机的操作进行直接向下遍历不进行返回最后 pushup 就行了。

考虑证明这样操作的复杂度的正确性，因为一次暴力的更改 $lmx$ 只会遍历其所有的祖先而后移操作又是一个罕见操作，所以总共的时间复杂度就是 $O(n\log ^2 n)$。

于是我们就得到了 $O((q+n)\log ^2n)$ 的优秀做法。

P3676 小清新数据结构题

用书剖把这个问题拍到序列上面，考虑在数列上怎么处理。

假设根都是 $1$，那么给一个点单点加就只会影响其祖先的子树大小，那么就有：

$\sum (S_i+V)^2=(\sum S_i)^2+2V\times \sum S_i + V^2\times len$

考虑换根，假设现在把根换成 $x$，那么就只有 $1$ 到 $x$ 这个路径上的节点的子树大小会变化，那么设 $a_i$ 为以 $1$ 为根路径上的子树和，$b_i$ 为以 $x$ 为根路径上的子树和。

于是就有：

$ans_x=ans_1-\sum\limits {a_i}^2+\sum {b_i}^2$

然而因为：

$a_i+b_{i+1}=a_0$

所以就有：

$ans_x=ans_1+(k-1) {a_0}^2-2a_0\sum a_i$

其中 $k$ 是 $x$ 到 $1$ 的距离，时间复杂度为 $O(n\log^2 n)$。

CF1034D Intervals of Intervals

考虑查询一个区间 $[l,r]$ 的贡献怎么做，容易想到扫描线。

依次增加右端点，当右端点 $i$ 满足 $i=r$ 时统计 $[l,i]$ 的贡献，每一次操作把 $[a_i,b_i]$ 推平成 $i$。

查询 $[l,i]$ 的答案时就只需要统计有多少位置的值不小于 $l$ 就行了。

那么用 ODT 维护这个东西，把原本的区间推平改为一些区间。

回到原本的问题，显然可以二分出第 $k$ 大的区间有多少，最后把这些区间全都加起来。

注意到如果 $[l,r]$ 的并是大于二分值的，那么左端点小于等于 $l$ 右端点是 $r$ 的区间都满足，那么我们显然和可以双指针维护这个东西。

有大佬告诉我们两个 $\log$ 似乎会寄掉，考虑把现在一堆 $\log$ 的复杂度降下来。

容易理解，其实每次操作的珂朵莉树都是一样的那么把这个修改提前拿出来，这样就把珂朵莉的 $\log$ 优化没了。

对于添加一个线段，其对于贡献是连续的，那么我们可以通过前缀和的方式将区间加转化为单点加，在双指针的同时对我们维护的这个东西进行前缀和，于是一个 $\log$ 做完了。

很牛逼的题目，思路很简单但是很难想而且也很有用。

Ynoi2019 魔法少女网站

先考虑没有修改的情况，我们令 $b_i=[a_i\le x]$，那么题目要求的就是 $b_i=1$ 的极长连续段的长度 $\sum \dfrac{siz\times (siz-1)}{2}$。

但是现在有很多 $x$，所以我们遇到的问题就是把一些位置 $0\gets 1$ 和 $1\gets 0$。

$1\gets 0$ 维护起来太慢了，而 $0\gets 1$ 就是区间合并和单点修改，是容易处理的。

那么我们将所有的 $x$ 从小到大排序，这样我们就可以保证所有操作都是 $0\gets 1$。

那么我们开一个数组记录那些数被修改了，对于全部操作都没有修改的数，我们按照静态的方法去修改，对于被修改的数我们假设其为极大值。

接下来对于每一个询问暴力操作修改，我们将其看作了极大值所以不会存在 $1\gets 0$ 的情况，直接把原本两侧区间的贡献减去再加上现在的贡献就行了。

需要注意对于一个询问可能有多个修改都可以作用到身上，所以需要注意实现时的正确性。

但是现在的时间复杂度是 $O(m^2)$ 的，显然无法通过，考虑对操作分块。

每 $\sqrt{m}$ 个操作为一块，于是现在复杂度就是 $O(m\sqrt m)$ 的了。