lct是一种动态树,用来维护一些动态加边删边的操作的东西.他主要用到几个操作,其实这个算法和树链刨分有点像,但是不能用线段树简单维护,所以我们要用多棵平衡树来维护树上的一个个子树,然后就进行一些很秀的操作.详情见这个博客:FlashHu

这个博客讲的是真的好,特别适合新手看,而且特别细节,(特别带劲).现在我就可以上代码:

模板:

#include <iostream>

#include <cassert>

#include <cstdio>

#include <cmath>

#include <ctime>

#include <queue>

#include <algorithm>

#include <cstring>

using namespace std;

#define duke(i, a, n) for (register int i = a; i <= n; i++)

#define lv(i, a, n) for (register int i = a; i >= n; i--)

#define clean(a) memset(a, 0, sizeof(a))

const int INF =  << ;

typedef long long ll;

typedef double db;

template <class T>

void read(T &x) {

    char c;

    bool op = ;

    while (c = getchar(), c < '' || c > '')

        if (c == '-')

            op = ;

    x = c - '';

    while (c = getchar(), c >= '' && c <= '') x = x *  + c - '';

    if (op)

        x = -x;

}

template <class T>

void write(T x) {

    if (x < )

        putchar('-'), x = -x;

    if (x >= )

        write(x / );

    putchar('' + x % );

}

const int N = ;

struct node {

    int fa, ch[], rev, v, s;

} a[N];

int st[N];

#define O(a) cout << #a << " "  << a << endl;

int n, m;

bool isroot(int x) { return !(a[a[x].fa].ch[] == x || a[a[x].fa].ch[] == x); }

void pushr(int x) {

    swap(a[x].ch[], a[x].ch[]);

    a[x].rev ^= ;

}

void push_down(int k) {

    if (a[k].rev) {

        if (a[k].ch[])

            pushr(a[k].ch[]);

        if (a[k].ch[])

            pushr(a[k].ch[]);

        a[k].rev ^= ;

    }

}

void push_up(int x) { a[x].s = a[a[x].ch[]].s ^ a[a[x].ch[]].s ^ a[x].v; }

void connect(int x, int fa, int son) {

    a[x].fa = fa;

    a[fa].ch[son] = x;

}

int iden(int x) { return a[a[x].fa].ch[] == x ?  : ; }

void rotate(int x) {

    int y = a[x].fa;

    int mroot = a[y].fa;

    int mrootson = iden(y);

    int yson = iden(x);

    int b = a[x].ch[yson ^ ];

    if (!isroot(y)) {

        a[mroot].ch[mrootson] = x;

    }

    a[x].fa = mroot;

    connect(b, y, yson);

    connect(y, x, yson ^ );

    push_up(y);

    push_up(x);

}

void splay(int x) {

    int top = ;int  i;

    st[++top] = x;

    for (i = x; !isroot(i); i = a[i].fa) {

        st[++top] = a[i].fa;

    }

    for (int i = top; i >= ; i--) {

        push_down(st[i]);

    }

    while (!isroot(x)) {

        int y = a[x].fa;

        if (isroot(y)) {

            rotate(x);

        } else if (iden(x) == iden(y)) {

            rotate(y);

            rotate(x);

        } else {

            rotate(x);

            rotate(x);

        }

    }

    push_up(x);

}

void access(int x) {

    int t = ;

    while (x) {

        splay(x);

        a[x].ch[] = t;

        push_up(x);

        t = x;

        x = a[x].fa;

    }

}

void make_root(int x) {

    access(x);

    splay(x);

    //    a[a[x].ch[0]].rev ^= 1;

    //    a[a[x].ch[1]].rev ^= 1;

    pushr(x);

    //    swap(a[x].ch[0],a[x].ch[1]);

    //    push_down(x);

}

void split(int x, int y) {

    // if (x <= n && y <= n) {

        make_root(x);

        access(y);

        splay(y);

    // }

}

int findroot(int x) {

    access(x);

    splay(x);

    push_down(x);

    while (a[x].ch[]){

        push_down(a[x].ch[]);

        x = a[x].ch[];

    }

    return x;

}

void link(int x, int y) {

    make_root(x);

    int t = findroot(y);

    assert(t);

    if ( t != x)

        a[x].fa = y;

}

void cut(int x, int y) {

    make_root(x);

    int t = findroot(y);

    assert(t);

    if (t == x && a[x].fa == y && !a[x].ch[]) {

        a[x].fa = a[y].ch[] = ;

        push_up(y);

    }

}

int main() {

//    freopen("in.in","r",stdin);

    int x, y, typ;

    read(n);

    read(m);

    duke(i, , n) { read(a[i].v); push_up(i); }

    int oup = ;

    duke(mi,,m){

        read(typ);

        read(x);

        read(y);

        if (typ == ) {

            split(x, y);

            printf("%d\n", a[y].s);

            ++oup;

        } else if (typ == ) {

            link(x, y);

        } else if (typ == ) {

            cut(x, y);

        } else {

            splay(x);

            a[x].v = y;

        }

        //        cout<<a[1].ch[0]<<" "<<a[1].ch[1]<<" "<<a[1].fa<<" "<<a[1].v<<" "<<a[1].s<<endl;

    }

    return ;

}

魔法森林:

// luogu-judger-enable-o2

#include<iostream>

#include<cstdio>

#include<cmath>

#include<ctime>

#include<queue>

#include<algorithm>

#include<cstring>

using namespace std;

#define duke(i,a,n) for(register int i = a;i <= n;i++)

#define lv(i,a,n) for(register int i = a;i >= n;i--)

#define clean(a) memset(a,0,sizeof(a))

const int INF =  << ;

typedef long long ll;

typedef double db;

template <class T>

void read(T &x)

{

    char c;

    bool op = ;

    while(c = getchar(), c < '' || c > '')

        if(c == '-') op = ;

    x = c - '';

    while(c = getchar(), c >= '' && c <= '')

        x = x *  + c - '';

    if(op) x = -x;

}

template <class T>

void write(T x)

{

    if(x < ) putchar('-'), x = -x;

    if(x >= ) write(x / );

    putchar('' + x % );

}

#define min2(x,y) if(x>y)x=y;

const int N = 2e5 + ;

const int P = ;

struct node

{

    int fa,ch[],rev,v,mx;

}a[N];

int st[N],n,m;

struct edge

{

    int u,v,a,b;

    bool operator < (const edge &oth) const

    {

        return a < oth.a;

    }

    void getin()

    {

        read(u);read(v);

        read(a);read(b);

        u |= P;v |= P;

    }

}e[ * N];

bool isroot(int x)

{

    return a[a[x].fa].ch[] != x && a[a[x].fa].ch[] != x;

}

void pushr(int x)

{

    swap(a[x].ch[],a[x].ch[]);

    a[x].rev ^= ;

}

void push_down(int x)

{

    if(a[x].rev)

    {

//        if(a[a[x].ch[0]].rev) pushr(a[x].ch[0]);

//        if(a[a[x].ch[1]].rev) pushr(a[x].ch[1]);

        swap(a[x].ch[],a[x].ch[]);

        a[a[x].ch[]].rev ^= ;

        a[a[x].ch[]].rev ^= ;

        a[x].rev ^= ;

    }

}

void push_up(int x)

{

    a[x].mx = x;

    if(e[a[x].mx].b < e[a[a[x].ch[]].mx].b) a[x].mx = a[a[x].ch[]].mx;

    if(e[a[x].mx].b < e[a[a[x].ch[]].mx].b) a[x].mx = a[a[x].ch[]].mx;

}

int iden(int x)

{

    return a[a[x].fa].ch[] == x ?  : ;

}

void connect(int x,int fa,int son)

{

    a[x].fa = fa;

    a[fa].ch[son] = x;

}

void rotate(int x)

{

    int y = a[x].fa;

    int mroot = a[y].fa;

    int mrootson = iden(y);

    int yson = iden(x);

    int b = a[x].ch[yson ^ ];

    if(!isroot(y))

    {

        a[mroot].ch[mrootson] = x;

    }

    a[x].fa = mroot;

    connect(y,x,yson ^ );

    connect(b,y,yson);

    push_up(y);

//    update(x);

}

void splay(int x)

{

    int top = ,i;

    st[++top] = x;

    for(i = x;!isroot(i);i = a[i].fa)

    {

        st[++top] = a[i].fa;

    }

    push_down(a[i].fa);

    for(int i = top;i;i--)

    {

        push_down(st[i]);

    }

    while(!isroot(x))

    {

        int y = a[x].fa;

        if(isroot(y)) rotate(x);

        else if(iden(x) == iden(y))

        {

            rotate(y);rotate(x);

        }

        else

        {

            rotate(x);rotate(x);

        }

    }

    push_up(x);

}

void access(int x)

{

    int t = ;

    while(x)

    {

        splay(x);

        a[x].ch[] = t;

        push_up(x);

        t = x;

        x = a[x].fa;

    }

}

void makeroot(int x)

{

    access(x);

    splay(x);

    a[x].rev ^= ;

}

int findroot(int x)

{

    access(x);

    splay(x);

    while(a[x].ch[])

    x = a[x].ch[];

    return x;

}

void link(int x)

{

    int y = e[x].u,z = e[x].v;

    makeroot(z);

    a[a[z].fa = x].fa = y;

//    a[x].fa = y;

}

void cut(int x)

{

    access(e[x].v);

    splay(x);

    a[x].ch[] = a[x].ch[] = a[a[x].ch[]].fa = a[a[x].ch[]].fa = ;

    push_up(x);

}

int main()

{

//    freopen("2387.in","r",stdin);

    int ans = INF;

    read(n);read(m);

    duke(i,,m)

    {

        e[i].getin();

    }

    sort(e + ,e + m + );

    int y,z;

    duke(i,,m)

    {

        if((y = e[i].u) == (z = e[i].v)) continue;

        makeroot(y);

        if(y != findroot(z)) link(i);

        else if(e[i].b < e[a[z].mx].b)

        {

            cut(a[z].mx);

            link(i);

        }

        makeroot( | P);

        if(( | P) == findroot(n | P))

        ans = min(ans,e[i].a + e[a[n | P].mx].b);

    }

    printf("%d\n",ans == INF ? - : ans);

    return ;

}

弹飞绵羊:

#include<iostream>

#include<cstdio>

#include<cmath>

#include<queue>

#include<algorithm>

#include<vector>

#include<complex>

#include<cstring>

using namespace std;

#define duke(i,a,n) for(int i = a;i <= n;i++)

#define lv(i,a,n) for(int i = a;i >= n;i--)

#define clean(a) memset(a,0,sizeof(a))

#define mp make_pair

#define cp complex<db>

#define enter puts("")

const long long INF = 1LL << ;

const double eps = 1e-;

typedef long long ll;

typedef double db;

template <class T>

void read(T &x)

{

    char c;

    bool op = ;

    while(c = getchar(), c < '' || c > '')

        if(c == '-') op = ;

    x = c - '';

    while(c = getchar(), c >= '' && c <= '')

        x = x *  + c - '';

    if(op) x = -x;

}

template <class T>

void write(T x)

{

    if(x < ) putchar('-'), x = -x;

    if(x >= ) write(x / );

    putchar('' + x % );

}

struct node

{

    int ch[],siz,fa;

}a[];

int n,m;

int iden(int x)

{

    return a[a[x].fa].ch[] == x ?  : ;

}

void connect(int x,int fa,int son)

{

    a[x].fa = fa;

    a[fa].ch[son] = x;

}

bool isroot(int x)

{

    return a[a[x].fa].ch[] != x && a[a[x].fa].ch[] != x;

}

void push_up(int x)

{

    a[x].siz = a[a[x].ch[]].siz + a[a[x].ch[]].siz + ;

}

/*void pushr(int x)

{

    swap(a[x].ch[0],a[x].ch[1]);

    a[x].rev ^= 1;

}

void push_down(int x)

{

    if(a[x].rev)

    {

        if(a[x].ch[0]) pushr(a[x].ch[0]);

        if(a[x].ch[1]) pushr(a[x].ch[1]);

        a[x].rev ^= 1;

    }

}*/

void rotate(int x)

{

    int y = a[x].fa;

    int mroot = a[y].fa;

    int mrootson = iden(y);

    int yson =iden(x);

    int b = a[x].ch[yson ^ ];

    if(!isroot(y))

    {

        a[mroot].ch[mrootson] = x;

    }

    a[x].fa = mroot;

    connect(b,y,yson);

    connect(y,x,yson ^ );

    push_up(y);

}

/*inline bool isroot(int x){

    return a[a[x].fa].ch[0]==x||a[a[x].fa].ch[1]==x;

}

void rotate(int x){

    int y=a[x].fa,z=a[y].fa,k=a[y].ch[1]==x,w=a[x].ch[!k];

    if(isroot(y))a[z].ch[a[z].ch[1]==y] = x;a[x].ch[!k]=y;a[y].ch[k]=w;

    if(w)a[w].fa=y;a[y].fa=x;a[x].fa=z;

    push_up(y);

}*/

void splay(int x)

{

    while(!isroot(x))

    {

        int y = a[x].fa;

        if(isroot(y)) rotate(x);

        else if(iden(x) == iden(y))

        {

            rotate(y);rotate(x);

        }

        else

        {

            rotate(x);rotate(x);

        }

    }

    push_up(x);

}

/*void splay(int x){

    int y,z;

    while(isroot(x)){

        y=a[x].fa;z=a[y].fa;

        cout<<x<<endl;

        if(isroot(y))

            rotate((a[y].ch[0]==x)^(a[z].ch[0]==y)?y:x);

        rotate(x);

    }

    push_up(x);

}*/

void access(int x)

{

    int t = ;

    while(x)

    {

        splay(x);

        a[x].ch[] = t;

        t = x;

        push_up(x);

        x = a[x].fa;

    }

}

int ch,j,k;

int main()

{

    // freopen("3203.in","r",stdin);

    read(n);

    duke(i,,n)

    {

        a[i].siz = ;

        read(k);

        if(i + k <= n)

        a[i].fa = i + k;

    }

    read(m);

    while(m--)

    {

        read(ch);

        if(ch == )

        {

            read(j);j++;

            access(j);splay(j);

            printf("%d\n",a[j].siz);

        }

        else

        {

            read(j);read(k); ++j;

            access(j);splay(j);

            a[j].ch[] = a[a[j].ch[]].fa = ;

            if(j + k <= n) a[j].fa = j + k;

            push_up(j);

        }

    }

    return ;

}

/*int main()

{

    freopen("3203.in","r",stdin);

    register char ch;

    int n,m,j,k;

    read(n);

    for(j=1;j<=n;++j){

        a[j].siz=1;

        read(k);

        if(j+k<=n)a[j].fa=j+k;//如果弹飞了就不连边

    }

    read(m);

    int op = 0;

    while(m--){

        read(op);

        if(op&1){

            read(j);++j;

            access(j);splay(j);//直接查询

            printf("%d\n",a[j].siz);

        }

        else{

            read(j);read(k);++j;

            access(j);splay(j);

            a[j].ch[0]=a[a[j].ch[0]].fa=0;//直接断边

            if(j+k<=n)a[j].fa=j+k;//直接连边

            push_

            up(j);

        }

    }

    return 0;

}*/

洞穴勘测:

#include<iostream>

#include<cstdio>

#include<cmath>

#include<ctime>

#include<queue>

#include<algorithm>

#include<cstring>

using namespace std;

#define duke(i,a,n) for(register int i = a;i <= n;i++)

#define lv(i,a,n) for(register int i = a;i >= n;i--)

#define clean(a) memset(a,0,sizeof(a))

const int INF =  << ;

typedef long long ll;

typedef double db;

template <class T>

void read(T &x)

{

    char c;

    bool op = ;

    while(c = getchar(), c < '' || c > '')

        if(c == '-') op = ;

    x = c - '';

    while(c = getchar(), c >= '' && c <= '')

        x = x *  + c - '';

    if(op) x = -x;

}

template <class T>

void write(T x)

{

    if(x < ) putchar('-'), x = -x;

    if(x >= ) write(x / );

    putchar('' + x % );

}

struct node

{

    int fa,ch[],rev;

}a[];

int n,m,st[];

bool isroot(int x)

{

    return a[a[x].fa].ch[] != x && a[a[x].fa].ch[] != x;

}

void push_down(int k)

{

    if(a[k].rev)

    {

        int l = a[k].ch[];

        int r = a[k].ch[];

        a[k].rev ^= ;

        a[l].rev ^= ;

        a[r].rev ^= ;

        swap(a[k].ch[],a[k].ch[]);

    }

}

int iden(int x)

{

    return a[a[x].fa].ch[] == x ?  : ;

}

void connect(int x,int f,int son)

{

    a[x].fa = f;

    a[f].ch[son] = x;

}

void rotate(int x)

{

    int y = a[x].fa;

    int mroot = a[y].fa;

    int mrootson = iden(y);

    int yson = iden(x);

    int b = a[x].ch[yson ^ ];

    if(!isroot(y))

    {

        a[mroot].ch[mrootson] = x;

    }

    a[x].fa = mroot;

    connect(b,y,yson);

    connect(y,x,yson ^ );

}

void splay(int x)

{

    int top = ;

    st[++top] = x;

    for(int i = x;!isroot(i);i = a[i].fa)

    {

        st[++top] = a[i].fa;

        // cout<<"gg"<<endl;

    }

    // cout<<"out"<<endl;

    for(int i = top;i;i--)

    push_down(st[i]);

    while(!isroot(x))

    {

        int y = a[x].fa;

        if(isroot(y)) rotate(x);

        else if(iden(x) == iden(y))

        {

            rotate(y);rotate(x);

        }

        else

        {

            rotate(x);rotate(x);

        }

        // cout<<"233"<<endl;

    }

}

void access(int x)

{

    int t = ;

    while(x)

    {

        splay(x);

        a[x].ch[] = t;

        t = x;

        x = a[x].fa;

    }

}

void rever(int x)

{

    access(x);

    splay(x);

    a[x].rev ^= ;

}

void link(int x,int y)

{

    rever(x);a[x].fa = y;

    splay(x);

    // cout<<x<<" "<<y<<endl;

}

void cut(int x,int y)

{

    rever(x);

    access(y);

    splay(y);

    a[y].ch[] = a[x].fa = ;

}

int find(int x)

{

//    cout<<x<<endl;

    access(x);//cout<<"yes"<<endl;

    splay(x);

    int y = x;

    //cout<<"!!!"<<y<<endl;

    while(a[y].ch[])

    y = a[y].ch[];

    // cout<<y<<endl;

    return y;

}

int main()

{

    // freopen("2147.in","r",stdin);

    char ch[];

    int x,y;

    read(n);read(m);

    duke(i,,m)

    {

        scanf("%s",ch);

        read(x);read(y);

        if(ch[] == 'C') link(x,y);

        else if(ch[] == 'D') cut(x,y);

        else

        {

            if(find(x) == find(y)) printf("Yes\n");

            else

            printf("No\n");

        }

    }

    return ;

}

最新文章

  1. [转]excel set drop-down values based on vlookup
  2. 【转载】Visual Studio 2015 for Linux更好地支持Linux下的开发
  3. Codeforces Round #318(Div 1) 573A, 573B,573C
  4. Linux 环境变量详解
  5. selenium多个标签页的切换（弹出新页面的切换）
  6. css3部分整理
  7. private static final 修饰符
  8. ES6箭头函数Arrow Function
  9. oracle 常见查询题
  10. linux如何复制文件夹和移动文件夹
  11. 展示博客---Alpha版本展示
  12. FFmpeg数据结构AVFrame
  13. 一份C++学习资源，咬牙切齿地好用呀
  14. PHP隐藏版本号教程
  15. Linux学习笔记：JDK安装
  16. tms web core pwa让你的WEB APP离线可用
  17. GitHub出现Permissiondenied (publickey).
  18. Swagger与SpringMVC整合
  19. ip地址后边加个/8(16,24,32)是什么意思
  20. yum的repo文件详解、以及epel简介、yum源的更换

热门文章

  1. 查询条件中,不进sql语句 也不进后台bug
  2. xmpp聊天室(5)
  3. python whl模块安装方法
  4. 【Linux软件安装】
  5. TestNG分组测试
  6. 解决Python打包exe控制台无法粘贴问题
  7. https://segmentfault.com/a/1190000012844836---------关于SpringBoot上传图片的几种方式
  8. Scala解析Json格式
  9. Spring 进行junit单元测试时，出现method ‘initializationError’ 错误
  10. 【GC分析】Java GC日志查看