[BZOJ4530/LOJ2230][Bjoi2014]大融合(LCT)

发布于 2018-01-22  76 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ4530/LOJ2230][Bjoi2014]大融合(LCT)

Description

小强要在 N个孤立的星球上建立起一套通信系统。这套通信系统就是连接 N 个点的一个树。这个树的边是一条一条添加上去的。在某个时刻,一条边的负载就是它所在的当前能够联通的树上路过它的简单路径的数量。
BZOJ4530
例如,在上图中,现在一共有了5条边。其中,(3,8)这条边的负载是6,因
为有六条简单路径2-3-8,2-3-8-7,3-8,3-8-7,4-3-8,4-3-8-7路过了(3,8)。
现在,你的任务就是随着边的添加,动态的回答小强对于某些边的负载的
询问。

Http

BZOJ
权限题,本站离线版本:bzojch
LOJ

Tag

LCT

题目大意

动态维护子树和

解决思路

根据乘法原理,就是动态求每一次两边的子树和。
那么由于\(LCT\)的\(size\)只能维护它实儿子的\(size\)之和,对于虚儿子没有办法处理,所以我们对于每一个点再记一个其虚儿子的大小记为\(vsize\)。那么修改这个虚儿子大小的地方就是\(LCT\)中修改边的虚实关系的时候,即\(Link\)操作和\(Access\)操作,在相应的地方修改即可

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=100010;
const int inf=2147483647;

class Splay_Data
{
public:
    int fa,ch[2];
    int size,vsize;
    int rev;
};

int n;
Splay_Data S[maxN];
int Stack[maxN];

bool Isroot(int x);
void Update(int x);
void PushDown(int x);
void Rotate(int x);
void Splay(int x);
void Access(int x);
void Makeroot(int x);
int Findroot(int x);
void Split(int x,int y);
void Link(int x,int y);
void Cut(int x,int y);

int main()
{
    int Q;
    scanf("%d%d",&n,&Q);
    for (int i=1;i<=n;i++) S[i].size=1,S[i].vsize=0;
    while (Q--)
    {
        char opt;cin>>opt;
        int x,y;scanf("%d%d",&x,&y);
        if (opt=='A') Link(x,y);
        if (opt=='Q')
        {
            Split(x,y);
            printf("%lld\n",1ll*(ll)(S[y].size-S[x].size)*(ll)S[x].size);
        }
    }
    return 0;
}

bool Isroot(int x)
{
    if ((S[S[x].fa].ch[0]==x)||(S[S[x].fa].ch[1]==x)) return 0;
    return 1;
}

void Update(int x)
{
    S[x].size=S[S[x].ch[0]].size+S[S[x].ch[1]].size+1+S[x].vsize;
    return;
}

void PushDown(int x)
{
    if (S[x].rev)
    {
        S[x].rev=0;
        int lson=S[x].ch[0],rson=S[x].ch[1];
        swap(S[lson].ch[0],S[lson].ch[1]);
        swap(S[rson].ch[0],S[rson].ch[1]);
        if (lson) S[lson].rev^=1;
        if (rson) S[rson].rev^=1;
    }
    return;
}

void Rotate(int x)
{
    int y=S[x].fa,z=S[y].fa;
    int sx=(x==S[y].ch[1]);
    int sy=(y==S[z].ch[1]);
    S[x].fa=z;if (Isroot(y)==0) S[z].ch[sy]=x;
    S[y].ch[sx]=S[x].ch[sx^1];if (S[x].ch[sx^1]) S[S[x].ch[sx^1]].fa=y;
    S[y].fa=x;S[x].ch[sx^1]=y;
    Update(y);
    return;
}

void Splay(int x)
{
    int now=x;
    int stacktop=1;Stack[stacktop]=x;
    while (Isroot(now)==0)
    {
        Stack[++stacktop]=S[now].fa;
        now=S[now].fa;
    }
    for (int i=stacktop;i>=1;i--) PushDown(Stack[i]);
    while (Isroot(x)==0)
    {
        int y=S[x].fa,z=S[y].fa;
        if (Isroot(y)==0)
            ((x==S[y].ch[0])^(y==S[z].ch[0]))?(Rotate(x)):(Rotate(y));
        Rotate(x);
    }
    Update(x);
    return;
}

void Access(int x)
{
    int lastx=0;
    while (x)
    {
        Splay(x);S[x].vsize=S[x].vsize+S[S[x].ch[1]].size-S[lastx].size;//注意这里对vsize的操作
        S[x].ch[1]=lastx;S[lastx].fa=x;
        Update(x);
        lastx=x;x=S[x].fa;
    }
    return;
}

void Makeroot(int x)
{
    Access(x);Splay(x);S[x].rev^=1;swap(S[x].ch[0],S[x].ch[1]);
    return;
}

int Findroot(int x)
{
    Access(x);Splay(x);
    int now=x;
    while (S[now].ch[0]) now=S[now].ch[0];
    return now;
}

void Split(int x,int y)
{
    Makeroot(x);Access(y);Splay(y);
    return;
}

void Link(int x,int y)
{
    Makeroot(x);Makeroot(y);//注意这里也要makeroot(y)
    S[x].fa=y;S[y].vsize+=S[x].size;
    Update(y);
    return;
}

void Cut(int x,int y)
{
    Split(x,y);
    if (S[y].ch[0]!=x) return;
    S[y].size-=S[x].size;
    S[x].fa=S[y].ch[0]=0;
    return;
}

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ4530/LOJ2230][Bjoi2014]大融合(LCT)


HNCJ OIer 一枚