洛谷P3690 【模板】Link Cut Tree (LCT)

2018-06-17 20:43:52来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

题目背景

动态树

题目描述

给定n个点以及每个点的权值,要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。

0:后接两个整数(x,y),代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。

1:后接两个整数(x,y),代表连接x到y,若x到y已经联通则无需连接。

2:后接两个整数(x,y),代表删除边(x,y),不保证边(x,y)存在。

3:后接两个整数(x,y),代表将点x上的权值变成y。

输入输出格式

输入格式:

 

第1行两个整数,分别为n和m,代表点数和操作数。

第2行到第n+1行,每行一个整数,整数在[1,10^9]内,代表每个点的权值。

第n+2行到第n+m+1行,每行三个整数,分别代表操作类型和操作所需的量。

 

输出格式:

 

对于每一个0号操作,你须输出x到y的路径上点权的xor和。

 

输入输出样例

输入样例#1: 复制
3 3 
1
2
3
1 1 2
0 1 2 
0 1 1
输出样例#1: 复制
3
1

说明

数据范围: 1 \leq N, M \leq 3 \cdot {10}^51N,M3105

 

 

看了一下午的讲解

看了一晚上的代码

算是差不多理解了,不过还有一个潜在的隐患没有解决,就是代码里那个玄学的pushdown函数

等搞懂了再整理吧

 

// luogu-judger-enable-o2
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=3 * 1e5 + 10;
inline int read()
{
    char c = getchar();int x = 0,f = 1;
    while(c < '0' || c > '9'){if(c == '-')f = -1;c = getchar();}
    while(c >= '0' && c <= '9'){x = x * 10 + c - '0',c = getchar();}
    return x * f;
}
#define fa(x) T[x].f
#define ls(x) T[x].ch[0]
#define rs(x) T[x].ch[1]
int v[MAXN];
struct node {
    int f, ch[2], s;
    bool r;
}T[MAXN];
int ident(int x) {
    return T[fa(x)].ch[0] == x ? 0 : 1;//判断该节点是父亲的哪个儿子 
}
int connect(int x,int fa,int how) {
    T[x].f=fa;
    T[fa].ch[how]=x;//连接 
}
inline bool IsRoot(int x) {//若为splay中的根则返回1 否则返回0 
    return ls( fa(x) ) != x && rs( fa(x) ) != x;
    //用到了两个性质
    //1.若x与fa(x)之间的边是虚边,那么它的父亲的孩子中不会有他(不在同一个splay内)
    //2. splay的根节点与其父亲之间的边是虚边 
}
void update(int x) {
    T[x].s = T[ls(x)].s ^ T[rs(x)].s ^ v[x];//维护路径上的异或和 
}
void pushdown(int x) {
    if(T[x].r) {
        swap(ls(x),rs(x));
        T[ls(x)].r ^= 1;
        T[rs(x)].r ^= 1;
        T[x].r = 0;//标记下传 
    }
}
void rotate(int x) {
    int Y = T[x].f, R = T[Y].f, Yson = ident(x), Rson = ident(Y);
    int B = T[x].ch[Yson ^ 1];
    //Q为什么要这样写 ********************************************
    
    T[x].f = R;
    if(!IsRoot(Y))
        connect(x, R, Rson);
    //这里如果不判断y是否根节点,那么当y是根节点的时候,0节点的儿子就会被更新为x
    //这样x就永远不能被判断为根节点,也就会无限循环下去了
    //但是这里不更新x的父亲的话就会出现无限递归的情况 
    connect(B, Y, Yson);
    connect(Y, x, Yson ^ 1);
    update(Y); update(x);
}
int st[MAXN];
void splay(int x) {
    int y = x, top = 0;
    st[++top] = y;
    while(!IsRoot(y)) st[++top] = y = fa(y);
    while(top) pushdown(st[top--]);
    //因为在旋转的时候不会处理标记,所以splay之前应该下传所有标记 
    for(int y = fa(x); !IsRoot(x); rotate(x), y = fa(x))//只要不是根就转 
        if(!IsRoot(y)) 
            rotate( ident(x) == ident(y) ? x : y );
}
void access(int x) {//访问x节点 
    for(int y = 0; x; x = fa(y = x))
        splay(x), rs(x) = y, update(x);
    //首先把x splay到所在平衡树的根,这样可以保证它的右孩子就是在原树中对应的重链(右孩子深度比它大)
    //y是splay中x的儿子,把x的右儿子改成y,也就是把x和y之间的边变成实边
    //更改了节点顺序,需要update 
}
void makeroot(int x) {//把x改为原树的根节点 
    access(x);
    splay(x);
    T[x].r ^= 1;
    pushdown(x);
    //首先访问一下x,再把x转到根,
    //注意在access的时候都是连接的右儿子,这样会破坏顺序,因此我们需要将左右儿子翻转 
}
int findroot(int x) {//找到x在原树中的根节点 
    access(x);splay(x);
    while(ls(x)) x = ls(x);//找到深度最小的点即为根节点 
    return x;
}
void split(int x, int y) {
    makeroot(x);//首先把x置为根节点 
    access(y); splay(y);
    //然后访问一下y,再把y转到根节点,这样y维护的就是x - y 路径上的xor 
}
void link(int x, int y) {
    makeroot(x);//把x置为根节点 
    if(findroot(y) != x ) fa(x) = y;
    //如果x与y不在同一个splay中,就把y置为x的父亲 
    //因为不能判断x与y的深度,因此在这里不用更新y的儿子 
}
void cut(int x, int y) {
    makeroot(x);
    if(findroot(y) == x && fa(x) == y && !rs(x)) { 
        fa(x) = T[y].ch[0] = 0;
        update(y);
    }
    //注意findroot(y)之后,y会成为根节点 
    //对于第三个判断
    //可以构造出这样的树 
    // x
    // fuck
    // y
    //在splay中是这样的
    // y
    //x
    // fuck
    //这样很显然x与y是不相连的 
}
int main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    #else
    #endif
    int N = read(), M = read();
    for(int i = 1; i <= N; i++) v[i] = read();
    for(int i = 1; i <= M; i++) {
        int opt = read(), x = read(), y = read();
        if(opt == 0) split(x, y), printf("%d\n",T[y].s);
        else if(opt == 1) link(x, y);
        else if(opt == 2) cut(x, y);
        else if(opt == 3) splay(x), v[x] = y;
    }
    return 0;
}

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:【模板】矩阵快速幂

下一篇:BZOJ1969: [Ahoi2005]LANE 航线规划(LCT)