//我坚信LCT可以平替树剖
#include<bits/stdc++.h>
#define ls t[o].ch[0]
#define rs t[o].ch[1]
#define int long long
using namespace std;
const int N=500010;
const int inf=1e9;
int read() {
int x=0,f=1;
char ch=getchar();
while(ch<48||ch>57) {
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>=48&&ch<=57) {
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return x*f;
}
struct LCT {
int ch[2],fa;
int val,sum,tag;
//other_tag,other_values...
}t[N];
bool is_rt(int o) {//判断是否为根节点
int f=t[o].fa;
if(t[f].ch[0]!=o&&t[f].ch[1]!=o) return true;
else return false;
}
void rev(int o) {
if(!o) return;
swap(ls,rs);
t[o].tag^=1;
}
void push_up(int o) {
//...upd ls rs
return ;
}
void push_down(int o) {
//...other_tag
if(!t[o].tag) return ;
if(ls) rev(ls);
if(rs) rev(rs);
t[o].tag=0;
}
void push(int o) {//翻转整条链
if(!is_rt(o)) push(t[o].fa);
push_down(o);
}
void rotate(int o) {//rotate
int f=t[o].fa;
int g=t[f].fa;
int k=t[f].ch[1]==o;
if(!is_rt(f)) {
t[g].ch[t[g].ch[1]==f]=o;
}
t[o].fa=g;
t[f].ch[k]=t[o].ch[k^1];
if(t[o].ch[k^1]) t[t[o].ch[k^1]].fa=f;
t[f].fa=o;
t[o].ch[k^1]=f;
push_up(f);
}
void splay(int o) {//splay
int f,g;
push(o);
while(!is_rt(o)) {
f=t[o].fa;
g=t[f].fa;
if(!is_rt(f)) {
if((t[g].ch[0]==f)^(t[f].ch[0]==o)) rotate(o);
else rotate(f);
}
rotate(o);
}
push_up(o);
}
void access(int o) {//建立从原树根节点到x的一条实链
for(int i=0;o;i=o,o=t[o].fa) {
splay(o);
rs=i;
push_up(o);
}
}
void make_rt(int o) {//使x成为原树的根
access(o);
splay(o);
rev(o);//翻转ls与rs,维护中序遍历性质
}
void link(int x,int y) {//x,y之间连一条边
make_rt(x);
t[x].fa=y;
}
void split(int x,int y) {//建立从x-y的一条实链
make_rt(x);
access(y);
splay(y);//便利cut操作
}
void cut(int x,int y) {//剪断边(x,y)
split(x,y);
if(t[y].ch[0]!=x||t[x].ch[1]) return ;//保证x,y有直接一条边链接
t[y].ch[0]=t[x].fa=0;
push_up(x);
}
int LCA(int x,int y) {//lca
int lca;
access(x);
for(int i=0;y;i=y,y=t[y].fa) {
splay(y);
t[y].ch[1]=i;
push_up(y);
lca=y;
}
return lca;
}
int find_rt(int o) {//找到x在原树中的根节点
access(o);
splay(o);
while(ls) {
push_down(o);
o=ls;
}
return o;
}
signed main() {
return 0;
}
LCT板子
发布时间 2023-10-09 19:23:35作者: Diamondan