洛谷 P4219 [BJOI2014]大融合解题报告

P4219 [BJOI2014]大融合

题目描述

小强要在(N)个孤立的星球上建立起一套通信系统。这套通信系统就是连接(N)个点的一个树。这个树的边是一条一条添加上去的。在某个时刻，一条边的负载就是它所在的当前能够联通的树上路过它的简单路径的数量。

现在，你的任务就是随着边的添加，动态的回答小强对于某些边的负载的询问。

输入输出格式

输入格式：

第一行包含两个整数 (N, Q),表示星球的数量和操作的数量。星球从 (1) 开始编号。

接下来的 (Q) 行，每行是如下两种格式之一：

A x y 表示在 (x) 和 (y) 之间连一条边。保证之前 (x) 和 (y) 是不联通的。
Q x y表示询问 ((x,y)) 这条边上的负载。保证 (x) 和 (y) 之间有一条边。

输出格式：

对每个查询操作，输出被查询的边的负载。

说明

对于所有数据，(1≤N,Q≤10^5)

LCT维护子树信息，涨见识了。

(sizx_i)代表虚边连的儿子的大小。

然后(updata)这样写

void updata(int now){siz[now]=siz[ls]+siz[rs]+sizx[now]+1;}

然后是在(access)的时候修改一下虚边儿子大小，在(link)的时候要把两个树都选上去保证没得父亲，因为我们不想把被连的那个点的信息再向上更新。

维护最值可以在每个点开个平衡树

Code:

#include <cstdio>
#define ll long long
#define ls ch[now][0]
#define rs ch[now][1]
#define fa par[now]
const int N=1e5+10;
int ch[N][2],par[N],siz[N],sizx[N],tag[N],s[N],tot,tmp;
bool isroot(int now){return ch[fa][0]==now||ch[fa][1]==now;}
int identity(int now){return ch[fa][1]==now;}
void updata(int now){siz[now]=siz[ls]+siz[rs]+sizx[now]+1;}
void Reverse(int now){tag[now]^=1,tmp=ls,ls=rs,rs=tmp;}
void connect(int f,int now,int typ){ch[fa=f][typ]=now;}
void pushdown(int now)
{
    if(tag[now])
    {
        if(ls) Reverse(ls);
        if(rs) Reverse(rs);
        tag[now]^=1;
    }
}
void Rotate(int now)
{
    int p=fa,typ=identity(now);
    connect(p,ch[now][typ^1],typ);
    if(isroot(p)) connect(par[p],now,identity(p));
    else fa=par[p];
    connect(now,p,typ^1);
    updata(p),updata(now);
}
void splay(int now)
{
    while(isroot(now)) s[++tot]=now,now=fa;
    s[++tot]=now;
    while(tot) pushdown(s[tot--]);
    now=s[1];
    for(;isroot(now);Rotate(now))
        if(isroot(fa))
            Rotate(identity(now)^identity(fa)?now:fa);
}
void access(int now)
{
    for(int las=0;now;las=now,now=fa)
        splay(now),sizx[now]+=siz[rs]-siz[las],rs=las;
}
void evert(int now){access(now),splay(now),Reverse(now);}
void link(int u,int v){evert(u),access(v),splay(v),par[u]=v,sizx[v]+=siz[u],updata(v);}
void cat(int u,int v){evert(u),access(v),splay(v),ch[v][0]=par[u]=0,updata(v);}
int query(int now){access(now),splay(now);return siz[now];}
int n,q;
int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++) siz[i]=1;
    char op[3];
    for(int u,v,i=1;i<=q;i++)
    {
        scanf("%s%d%d",op,&u,&v);
        if(op[0]=='Q') cat(u,v),printf("%lld
",1ll*query(u)*query(v)),link(u,v);
        else link(u,v);
    }
    return 0;
}

2018.12.7