P2147 [SDOI2008]洞穴勘测

思路

没办法，我就是喜欢板子都想发的人

都是基础操作，不多说了

代码

#include <bits/stdc++.h>

#define ls ch[x][0]

#define rs ch[x][1]

#define FOR(i,a,b) for(int i=a;i<=b;++i)

using namespace std;

const int N=3e5+7;

int read() {

    int x=0,f=1;char s=getchar();

    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;

    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';

    return x*f;

}

int f[N],ch[N][2],lazy[N];

bool isroot(int x ) {return ch[f[x]][0]==x || ch[f[x]][1]==x;}

void tag(int x) {swap(ls,rs);lazy[x]^=1;}

void pushdown(int x) {

    if(lazy[x]) {

        tag(ls),tag(rs);

        lazy[x]=0;

    }

}

void rotate(int x) {

    int y=f[x],z=f[y],k=ch[y][1]==x,m=ch[x][k^1];

    if(isroot(y)) ch[z][ch[z][1]==y]=x;

    ch[x][k^1]=y;

    ch[y][k]=m;

    if(m) f[m]=y;

    f[x]=z;

    f[y]=x;

}

int Q[N];

void splay(int x) {

    int y=x,z=0;

    Q[++z]=y;

    while(isroot(y)) Q[++z]=y=f[y];

    while(z) pushdown(Q[z--]);

    while(isroot(x)) {

        y=f[x],z=f[y];

        if(isroot(y)) (ch[y][0]==x)^(ch[z][0]==y) ? rotate(x) : rotate(y);

        rotate(x);

    }

}

void access(int x) {

    for(int y=0;x;y=x,x=f[x])

        splay(x),rs=y;

}

void makeroot(int x) {

    access(x);

    splay(x);

    tag(x);

}

int findroot(int x) {

    access(x);

    splay(x);

    while(ls) pushdown(x),x=ls;

    return x;

}

void link(int x,int y) {

    makeroot(x);

    if(findroot(y)!=x) f[x]=y;

}

void cut(int x,int y) {

    makeroot(x);

    if(findroot(y)==x&&f[x]==y&&!ch[x][1]) {

        f[x]=ch[y][0]=0;

    }

}

int main() {

    int n=read(),m=read();

    char s[100];

    FOR(kkk,1,m) {

        scanf("%s",s);

        int x=read(),y=read();

        if(s[0]=='Q') {

            if(findroot(x)==findroot(y)) puts("Yes");

            else puts("No");

        } else if(s[0]=='C') link(x,y);

        else cut(x,y);

    }

    return 0;

}