可持久化数据结构

影魔

想到了离线的$n^2$做法，然后就不会了。

这里记录两个做法（%%%GPskyh和%%%素质先锋Lrefrain的）

抓住最值，一个点能作为最值的区间的范围可以找出来。

最主要的就是统计答案

1.先说skyh的 考虑到第一种情况非常好统计，我们试图在其中找出第二种情况的答案

我们先维护一个单调递减栈，发现第一种情况点对数是$O(n)$级别的，即只有一个点出栈和入栈的时候才会形成点对。

利用这个性质先把所有点对找出来，然后就可以直接扫了。

延续这个思路，我们发现，能形成情况二的点的是栈中的相邻元素，也就是说，新加进去的点对应着一段区间。

然后就是维护一棵线段树 从前往后扫，扫到一个点就把这个点对应的区间造成的贡献加进去，然后统计以这个点为右端点的区间答案。

线段树维护的是左端点的贡献，也就是我们在保证右端点合法的基础上利用线段树就可以进行降维打击。

我没有实现，只是口胡。

2.再说Lrefrain 假如我们有一个点对应的左右比它大的第一个数$l_i$,$r_i$，那么答案来自

1.[$l_i$,$r_i$]->p1

2.[$l_i$,$i+1$~$r_i-1$]->p2

3.[$l_i+1$~$i-1$,$r_i$]->p2

那我们怎么统计呢？

网上的做法是把区间化为点对，然后把情况2，3化为线段，每次询问视作一个矩阵。

但是现在我们可以有一个更简单的方法，维护一棵线段树，这颗线段树的含义是某一个端点在$i$的贡献，注意没有限定左还是右。

那我们一个询问的答案是某一端点在$l~r$的另一端点也在$l~r$的贡献。

这时候只需要在$l$-1处减去前面所有对$l~r$的贡献在$r$处加上就行了。美妙的差分！

常用套路：区间到点对的转化，固定一维，另一维用数据结构维护，差分思想的运用。

树上询问

关于维护一棵支持区间修改的主席树，我们不能下传标记，即标记永久化，但标记永久化需要注意一点就是更新的时候要加上自己懒标记的贡献，当我们统计一个区间的时候，只能利用这个来统计子树内部标记的贡献，也算是标记永久化的一个注意的地方，调了一下午。

注意思考问题一定要全面，标记永久化后不仅标记无法下传，而且标记对上面节点的贡献也无法统计！！！！所以维护sum的时候一定要加上标记贡献。

可持久化Trie板子：

1.自己YY的记录来自的位置，只能求区间异或一个数的最大值。

2.还有一种是记录每个节点的size，然后就可以利用这个来搞很多东西。

世博会：

用到了结论：切比雪夫距离和曼哈顿距离的转化：

$max(|x_1-x_2|,|y_1-y_2|)$ ->把两个点转化为$((x+y)/2,(x-y)/2)$，然后求两点曼哈顿距离。

用主席树来查找区间中位数就行了。