动态树基本概念
Splay
主要的操作函数
判断当前节点是否是根节点
// 判断_index是否是实链的顶部, 也就是另一条实链连向当前实链的虚边, 如果两个儿子都不是当前实链的节点, 那么当前点就是根节点
bool is_root(int _index) {
return tr[tr[_index].pre].son[0] != _index && tr[tr[_index].pre].son[1] != _index;
}
当前节点如果是跟节点, 那么该节点的pre一定是另一条实链的一个节点, 并且是虚边
由子节点更新父节点信息
void push_up(int _index) {
tr[_index].sum = tr[tr[_index].son[0]].sum ^ tr[_index].val ^ tr[tr[_index].son[1]].sum ;
}
将懒标记下传
// 反转当前节点的两个子节点
void push_rev(int _index) {
swap(tr[_index].son[0], tr[_index].son[1]);
tr[_index].rev ^= 1;
}
// 将当前节点的懒标记向下传递
void push_down(int _index) {
if (tr[_index].rev) {
push_rev(tr[_index].son[0]);
push_rev(tr[_index].son[1]);
tr[_index].rev = 0;
}
}
旋转操作
void rotate(int _index) {
int pre = tr[_index].pre;
int grand = tr[pre].pre;
int k = tr[pre].son[1] == _index;
// 当前旋转的点的父节点不能是根节点, 如果是根节点, 因为是虚边, 因此grand不能连向_index
if (!is_root(pre)) tr[grand].son[tr[grand].son[1] == pre] = _index;
tr[_index].pre = grand;
tr[pre].son[k] = tr[_index].son[k ^ 1], tr[tr[_index].son[k ^ 1]].pre = pre;
tr[_index].son[k ^ 1] = pre, tr[pre].pre = _index;
push_up(pre), push_up(_index);
}
如果grand
节点是另一条实链的节点, 因为是虚边, 因此不能从该节点连向当前节点
Splay操作
将当前点转到根节点
void splay(int _index) {
static int stk[NUMBER];
// 从当前点遍历到根节点, 然后从根节点向下传递懒标记
int top = 0, _node = _index;
stk[++top] = _node;
while (!is_root(_node)) stk[++top] = _node = tr[_node].pre;
while (top) push_down(stk[top--]);
while (!is_root(_index)) {
int pre = tr[_index].pre;
int grand = tr[pre].pre;
if (!is_root(pre)) {
if ((tr[grand].son[1] == pre) ^ (tr[pre].son[1] == _index)) rotate(_index);
else rotate(pre);
}
rotate(_index);
}
}
需要注意的是, 需要从当前节点开始向当前节点属于的root
进行压栈, 然后从root
向下先下传懒标记, 再进行Splay操作
LCT新的操作函数
access
操作
// 建立一条从根节点到_index的路径, 同时将_index变为对应实链的根节点
void access(int _index) {
int ver = _index;
// _index是上面的实链, y是下面的实链, 使_index沿着虚边向上走, 路径构成实链
for (int y = 0; _index; y = _index, _index = tr[_index].pre) {
splay(_index);
tr[_index].son[1] = y, push_up(_index);
}
splay(ver);
}
建立当前节点到所属根的实链路径, 并且将当前节点转到根节点
make_root
函数
// 将_index变为原树的根节点
void make_root(int _index) {
access(_index);
push_rev(_index);
}
首先将当前点和根节点进行access
, 然后因为是无根树, 所以可以将整棵树进行反转, 那么_index
就转到了根节点, 同时root
是当前树的中序遍历的最左侧节点
find_root
函数
int find_root(int _index) {
access(_index);
// 因为splay维护的信息一定是从上到下的, 因此将最下面的_index转到根节点, 那么根节点一定在当前splay的中序遍历的第一个节点
while (tr[_index].son[0]) {
push_down(_index);
_index = tr[_index].son[0];
}
splay(_index);
return _index;
}
找到_index
所属树的根节点, 向左寻找原根节点, 并且将其转到根节点的位置
split
函数
void split(int ver1, int ver2) {
make_root(ver1);
access(ver2);
}
将ver1
和ver2
之间变为实链没,前提是两个节点属于同一个Splay
当中
link
函数
void link(int ver1, int ver2) {
make_root(ver1);
if (find_root(ver2) != ver1) tr[ver1].pre = ver2;
}
如果ver
和ver2
不在一个Splay
中, 从ver1
所属的树连向ver2
所属的树, 也就是虚边
cut
函数
void cut(int ver1, int ver2) {
make_root(ver1);
// 判断ver2是否是ver1的后继, 只有是后继才能删除
if (find_root(ver2) == ver1 && tr[ver1].son[1] == ver2 && !tr[ver2].son[0]) {
tr[ver2].pre = tr[ver1].son[1] = 0;
push_up(ver1);
}
}
如果ver1
和ver2
之间存在实边, 删除
删除条件: 两个节点在一个树中
ver2
节点是ver1
节点的后继
完整代码
#include <iostream>
using namespace std;
const int NUMBER = 1e5 + 10;
int number, op_number;
struct Node {
int son[2], pre, val;
int rev, sum;
} tr[NUMBER];
// 判断_index是否是实链的顶部, 也就是另一条实链连向当前实链的虚边, 如果两个儿子都不是当前实链的节点, 那么当前点就是根节点
bool is_root(int _index) {
return tr[tr[_index].pre].son[0] != _index && tr[tr[_index].pre].son[1] != _index;
}
// 由子节点更新父节点
void push_up(int _index) {
tr[_index].sum = tr[tr[_index].son[0]].sum ^ tr[_index].val ^ tr[tr[_index].son[1]].sum ;
}
// 反转当前节点的两个子节点
void push_rev(int _index) {
swap(tr[_index].son[0], tr[_index].son[1]);
tr[_index].rev ^= 1;
}
// 将当前节点的懒标记向下传递
void push_down(int _index) {
if (tr[_index].rev) {
push_rev(tr[_index].son[0]);
push_rev(tr[_index].son[1]);
tr[_index].rev = 0;
}
}
void rotate(int _index) {
int pre = tr[_index].pre;
int grand = tr[pre].pre;
int k = tr[pre].son[1] == _index;
// 当前旋转的点的父节点不能是根节点, 如果是根节点, 因为是虚边, 因此grand不能连向_index
if (!is_root(pre)) tr[grand].son[tr[grand].son[1] == pre] = _index;
tr[_index].pre = grand;
tr[pre].son[k] = tr[_index].son[k ^ 1], tr[tr[_index].son[k ^ 1]].pre = pre;
tr[_index].son[k ^ 1] = pre, tr[pre].pre = _index;
push_up(pre), push_up(_index);
}
void splay(int _index) {
static int stk[NUMBER];
// 从当前点遍历到根节点, 然后从根节点向下传递懒标记
int top = 0, _node = _index;
stk[++top] = _node;
while (!is_root(_node)) stk[++top] = _node = tr[_node].pre;
while (top) push_down(stk[top--]);
while (!is_root(_index)) {
int pre = tr[_index].pre;
int grand = tr[pre].pre;
if (!is_root(pre)) {
if ((tr[grand].son[1] == pre) ^ (tr[pre].son[1] == _index)) rotate(_index);
else rotate(pre);
}
rotate(_index);
}
}
// 建立一条从根节点到_index的路径, 同时将_index变为对应实链的根节点
void access(int _index) {
int ver = _index;
// _index是上面的实链, y是下面的实链, 使_index沿着虚边向上走, 路径构成实链
for (int y = 0; _index; y = _index, _index = tr[_index].pre) {
splay(_index);
tr[_index].son[1] = y, push_up(_index);
}
splay(ver);
}
// 将_index变为原树的根节点
void make_root(int _index) {
access(_index);
push_rev(_index);
}
// 找到_index所在树的根节点
int find_root(int _index) {
access(_index);
// 因为splay维护的信息一定是从上到下的, 因此将最下面的_index转到根节点, 那么根节点一定在当前splay的中序遍历的第一个节点
while (tr[_index].son[0]) {
push_down(_index);
_index = tr[_index].son[0];
}
splay(_index);
return _index;
}
// 将ver1和ver2之间变为实链路径
void split(int ver1, int ver2) {
make_root(ver1);
access(ver2);
}
// 如果ver1和ver2不在一个splay中, 将ver1的实链连接到ver上
void link(int ver1, int ver2) {
make_root(ver1);
if (find_root(ver2) != ver1) tr[ver1].pre = ver2;
}
// 如果ver1到ver2之间存在边, 删除
void cut(int ver1, int ver2) {
make_root(ver1);
// 判断ver2是否是ver1的后继, 只有是后继才能删除
if (find_root(ver2) == ver1 && tr[ver1].son[1] == ver2 && !tr[ver2].son[0]) {
tr[ver2].pre = tr[ver1].son[1] = 0;
push_up(ver1);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cin >> number >> op_number;
for (int i = 1; i <= number; ++i) cin >> tr[i].val;
while (op_number--) {
int op, val1, val2;
cin >> op >> val1 >> val2;
if (op == 0) {
split(val1, val2);
cout << tr[val2].sum << endl;
}
else if (op == 1) {
link(val1, val2);
}
else if (op == 2) {
cut(val1, val2);
}
else {
splay(val1);
tr[val1].val = val2;
push_up(val1);
}
}
return 0;
}