闲话
似乎没几个人把闲话设为显示
但是我除了闲话没啥了
所以不隐藏了
而且主要的简介都在摘要里面了
我等一等再去切 risrqnis
我还剩五个点和55pts(
今天想到拉格朗日的英文名是 lagrange
然后 Lag Train 延误列车
所以 Lag Range 延误区间
[这里放一张延误列车的pv截图，记得以后补大图]
莫春者，春服既成，冠者五六人，童子六七人，浴乎沂，风乎舞雩，咏而归。
羊のような雲が浮かんだ昼すぎ
懐かしい歌が風に揺れている
あなたの声で教えて貰った言葉
今でも忘れぬように
書き留めてる同じことを
笛卡尔树
是树。一般化的笛卡尔树在每个点有两个权值 \((a_i,b_i)\)，对 \(a\) 满足堆性质，对 \(b\) 满足BST性质。
笛卡尔树在序列上建是很有用的。由此产生了四毛子等东西（
具体地，我们将序列的值赋作 \(a\)，将序列下标赋作 \(b\)。容易发现这样使得一段连续的区间在笛卡尔树上也连续，而且区间最大/小值是区间端点的 LCA。
关于建树：
考虑单调栈维护右链。我们从左到右扫序列，每次将当前元素插入单调栈，作为栈顶元素的对应儿子。
for (int i = 1; i <= n; i++) {
int k = top;
while (k > 0 && h[stk[k]] > h[i])
k--;
if (k)
rs[stk[k]] = i;
if (k < top)
ls[i] = stk[k + 1];
stk[++k] = i;
top = k;
}
然后就可以把序列问题转化成树上问题了。
应用1：四毛子算法
\(\text{Four Russian Algo [pre] [pre]} \ (\pm 1 RMQ)\)
给定一个序列，满足其差分序列只有 \(+1,-1\)。\(O(n) -O(1)\) 求区间最小值。
我们进行分块。设块长为 \(B = \frac {\log n} 2\)，则我们可以将区间最小值转化成三次最小值的最小值。如果我们能快速求得每块的最小值就可以通过ST表进行整块的维护。
考虑相邻元素之间差是 \(+1, -1\)，因此在一块内本质不同的情况只有 \(2^B = \sqrt n\) 种。我们预处理每种可能的 RMQ，这样带来的复杂度花费不会超过 \(O(n)\)。ST 表有复杂度 \(O(\frac nB log nB) = O(n)\).
因此有 \(O(n) -O(1)\) 区间最小值。
\(\text{Four Russian Algo [pre] (Faster LCA)}\)
给定一棵树。\(O(n) -O(1)\) 求两点 LCA。
我们跑出树的（拓展）欧拉序，每经过一条边就记录两端点。
然后两点第一次在这个序里出现的位置间深度最小的点就是 LCA。我们发现深度的变化是 \(\pm 1\)。于是问题转化成 \(\pm 1 RMQ\) 问题，如上求解就行。
\(\text{Four Russian Algorithm}\)
给定一个序列。\(O(n) -O(1)\) 求区间最小值。
跑出这个序列的笛卡尔树。
于是问题转化成快速 LCA 问题，如上求解就行。
这就是四毛子。
应用2：拓展(?)建树
即在一棵树上建出笛卡尔树。
做法和序列笛卡尔树一样，也是直接并入。具体按如下程序（大根堆）：
按权值扫描每个节点。扫描到一个节点时，判断所有与该节点相连的连通块。如果连通块的代表元小于该节点，则将该节点并入连通块，代表元设为该节点，并以该节点为父亲与代表元连边。
int fa[N];
int find(int x) { return x == fa[x] ? fa[x] : fa[x]=find(fa[x]); }
#define Aster(s, id) for ( register int i = head[s][id]; i; i = e[i].next )
int head[N][2], mlc;
struct node{
int to, next;
} e[N<<2];
void adde(int u, int v, int id) {
e[++mlc] = {v, head[u][id]};
head[u][id] = mlc;
rep(i,1,n) {
Aster(i, 0) {
int ret=find(e[i].v);
if(e[i].v < x and ret == x){
adde(x,ret,1);
fa[ret] = x;
}
}
}
\(\text{-SUPER- DouBlize}\)
给定一棵 \(n\) 个点的树，询问满足编号最小值为起点，最大值是终点的路径 \(x\rightarrow y\) 的数量。
\(n \le 1e6\).
构造两棵笛卡尔树，一棵小根一棵大根。问题转化成在两棵树上都是祖先子孙关系的节点对数。
跑出一棵树的dfs序，另一棵树进行dfs。dfs时将祖先在另一棵树上的dfs序插入树状数组，然后查询当前节点的dfs序区间就是答案。
主要是构造笛卡尔树，剩下的乱搞就行。