Splay
Splay
我们考虑在一颗 BST，用旋转操作将某个元素先提到根，使其仍是一颗 BST，这样的操作就是 \(s(x,0)\)。
void splay(int x,int target){while(fa[x]!=target){int f=fa[x],gf=fa[f];if(gf==target){rotate(x);break;}if(rson(gf,f)==rson(f,x)){rotate(f);}else{rotate(x);}rotate(x);}
}
目标：把 \(x\) 旋转至 \(target\) 下方。fa[x] 表示 \(x\) 的父节点。 rson(a,b) 表示 \(b\) 是否是 \(a\) 的右孩子。
Rotate
void rotate(int x){int f=fa[x],gf=fa[f];bool p=rson(f,x),q=!p;if(gf){ch[gf][rson(gf,f)]=x;}else{root=x;}fa[x]=gf;ch[f][p]=ch[x][q],fa[ch[x][q]]=f;ch[x][q]=f,fa[f]=x;push_up(f),push_up(x);
}
注意先更新 \(f\) 数据。
Delete
先 Find，再合并两颗子树。
切割区间 \([l,r]\)
可以先将 \(l-1\) 提到根，再将 \(r+1\) 提到 \(l-1\) 下方，后发现 \([l,r]\) 一定在 \(r+1\) 的左子树中。
Splay 习题
模糊的序列
题意
给出 \(a_i\in [l_i,r_i]\)，对于所有可能序列求最长严格上升子序列产长度最大值。其中 \(n\leq 3\times 10^5\)。
Sol
设 \(f_i\) 表示长度为 \(i\) 的 LIS 的最小结尾为 \(f_i\)，根据单调性 \(f_i<f_{i+1}\)，即 \(f_{i+1}\geq f_i+1\)。
现在考虑 \(a_i\in [l_i,r_i]\)。那么如果 \(\exists f_{i-1}<l\)，那么有 \(f_i=\min(f_i,l)\)，对于 \(l\leq f_{i-1}<r,f_i=\min(f_i,f_{i-1}+1)=f_{i-1}+1\)。
上述操作等于在区间 \([p,q]\)，在 \(p\) 处插入新 \(l\)，将原来的 \([p,q]\) 右移一位整体 \(+1\)。然后删除原本的 \(q+1\) 那个位置。等价于直接在 \(p\) 前插入 \(l\)，然后整体加 \(1\) 后删除 \(q+1\)。
Factories Once More
题意
原题
一棵树，选 \(k\) 个点设为关键点。求两两关键点距离之和最大值
Sol
树上 dp，然后观察到有凸性，后面明可夫斯基和合并。
LCT
动态树问题，即要求我们维护一个由若干棵子节点无序的有根树组成的森林。
要求这个数据结构支持对树的分割，合并，对某个点它到根的路径的某些操作。
Link-Cut Tree 是一种用来维护动态森林连通性的数据结构，适用于动态树问题。
它采用类似树链剖分的轻重边路径剖分，把树边分成实边和虚边，采用 Splay 维护每一条实路径。
基本操作均摊 \(O(\log n)\)，常数低于树剖。
LCT 的基本实现
每一条链对应着一个 Splay。
一些 Splay 构成了一个辅助树，每一颗辅助树维护一颗树，一些辅助树构成 LCT，其维护的是整个森林。
辅助树由多颗 Splay 组成，每颗 Splay 维护原树中的一条路径，且中序遍历这颗 Splay 得到的点序列，从前到后对应原树从上到下的一条路径。
Splay 根节点的父亲节点指向原树这个链的顶端的点的父亲节点，对应原树一条新边。
Splay 的中序遍历对应原树上链的遍历。
所以我们显然可以用辅助树还原出原树。
LCT 的操作
- Access(u)：访问某个节点 \(u\)，将根节点到 \(u\) 上的边都变为实边。
- MakeRoot(u)：将某个节点 \(u\) 置为所在树根节点，等价于把该节点到根所有边方向取反。
- Link(u,v)，连接 \(u,v\)。
- Cut(u,v)：分离 \(u,v\) 成两个树。
- FindRoot(u) 查询 \(u\) 所在树根节点。
- MakeTree()：向森林中种植一颗新的树。-
Access
不断将目前的点作为根旋转上去，然后连到新的父亲链的右儿子上。
int Access(int x){int p;for(p=0;x;p=x,x=f[x]){splay(x,0),ch[x][1]=p,push_up(x);}
}
通过势能分析可以得出均摊 \(O(\log n)\)。
MakeRoot
维护路径信息一定会出现路径深度无法严格递增的情况，根据辅助树的性质，这样的路径无法出现在 Splay 中。
考虑将树看为有向树，换根相当于将 \(u\) 到现根的路径方向换向。
发现先 Access(u) 后将 \(u\) 所在的 splay 翻转即可。
void MakeRoot(int x){x=Access(x);swap(ch[x][0],ch[x][1]);tag_swp[x]^=1;
}
FindRoot
先 Access(u)，由于根节点深度最小，我们在 \(u\) 所在的 Splay 中直接找出深度最小的点，注意下传懒标记。
int FindRoot(int u){u=Access(u);while(ch[u][0]){push_down(u);u=ch[u][0];}splay(u,0);return u;
}
Split
先 MakeRoot(u)，再 Access(v)。
void Split(int u,int v){MakeRoot(u);if(FindRoot(v)!=u){exit(1);}Access(v);
}
Link
先 MakeRoot(u)，然后将 \(u\) 的父亲指向 \(v\)。
void Link(int u,int v){MakeRoot(u);if(FindRoot(v)==u){return;}f[u]=v;
}
Cut
先 Split(u,v)，然后 splay(v)，由于此时 \(v\) 是根，那么 \(u\) 一定是 \(v\) 的儿子，那么双向断开即可。
void Cut(int u,int v){Split(u,v);splay(v,0);ch[v][0]=f[u]=0;
}
P3203 [HNOI2010] 弹飞绵羊
题意
对于 \(x\)，\(x\leftarrow x+k_x\)，求多少次 \(x>n\)，有带修改 \(k_i\)。
Sol(待补)
P1501 [国家集训队] Tree II
题意
一棵树，点权为 \(1\)。
- 将 \(u,v\) 路径加 \(c\)。
- 将 \((u,v)\) 边删掉，加上边 \((p,q)\) 保证仍未树。
- 路径乘 \(c\)。
- 求路径点权和。
Sol
LCT 懒标记下传。
P2387 [NOI2014] 魔法森林
题意
给无向图，求 \(1\) 到 \(n\) 路径上最小的 \(\max(a_i)+\max(b_i)\)。
\(n\leq 50000,m\leq 10^5\)
Sol
考虑暴力做法。按照 \(a_i\) 从小到达排序，一条条加边，每一次对于 \(b_i\) 做最小生成树，选取生成树最大的边与 \(a_i\) 求和，整个过程取最小值。
考虑优化。在最小生成树加入新边，产生一个环，我们只需删除环上最大边。
即：连接两个点，删除两个点的边，找路径最大值和路径位置。
P4299 首都
题意
维护森林，动态加边，询问某点所在树中心，询问所有树的重心异或和。两个重心找编号小的。
Sol
重心每个子树大小都不超过整个整棵树的一半。
把两棵树通过一条边连接成一棵树，新的重心一定在原来的两个重心的路径上。
向重心移动，最大子树大小一定在变小。我们记一下原来的重心 \(c_1,c_2\)。我们考虑 Cut 出 \(c_1,c_2\) 的路径。