BZOJ4530 BJOI2014大融合（线段树合并+并查集+dfs序）

时间：2024-01-12 18:34:02

易知所求的是两棵子树大小的乘积。先建出最后所得到的树，求出dfs序和子树大小。之后考虑如何在动态加边过程中维护子树大小。这个可以用树剖比较简单的实现，但还有一种更快更优美的做法就是线段树合并。对每个点开权值线段树，维护当前时刻这棵点为根的子树中，已经和其相连的点的dfs序情况。合并时直接将表示两棵子树的线段树合并，查询在整棵子树中查询某段dfs序区间。

也可以在线地用lct维护子树，并不会。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

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

    return x*f;

}

#define N 100010

int n,q,fa[N],dfn[N],p[N],root[N],size[N],t=,cnt=;

struct data{int x,y,op;

}Q[N];

struct data2{int to,nxt;

}edge[N<<];

struct data3{int l,r,x;

}tree[N<<];

void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}

int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}

void dfs(int k)

{

    dfn[k]=++cnt;size[k]=;

    for (int i=p[k];i;i=edge[i].nxt)

    if (!dfn[edge[i].to])

    {

        dfs(edge[i].to);

        size[k]+=size[edge[i].to];

    }

}

void add(int &k,int l,int r,int x)

{

    if (!k) k=++cnt;

    tree[k].x++;

    if (l==r) return;

    int mid=l+r>>;

    if (x<=mid) add(tree[k].l,l,mid,x);

    else add(tree[k].r,mid+,r,x);

}

int merge(int x,int y,int l,int r)

{

    if (!x||!y) return x|y;

    tree[x].x+=tree[y].x;

    int mid=l+r>>;

    tree[x].l=merge(tree[x].l,tree[y].l,l,mid),

    tree[x].r=merge(tree[x].r,tree[y].r,mid+,r);

    return x;

}

int query(int k,int l,int r,int x,int y)

{

    if (!k) return ;

    if (l==x&&r==y) return tree[k].x;

    int mid=l+r>>;

    if (y<=mid) return query(tree[k].l,l,mid,x,y);

    else if (x>mid) return query(tree[k].r,mid+,r,x,y);

    else return query(tree[k].l,l,mid,x,mid)+query(tree[k].r,mid+,r,mid+,y);

}

int main()

{

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

    freopen("bzoj4530.out","w",stdout);

    n=read(),q=read();

    for (int i=;i<=n;i++) fa[i]=i;

    for (int i=;i<=q;i++)

    {

        char c=getchar();

        while (c!='A'&&c!='Q') c=getchar();

        Q[i].x=read(),Q[i].y=read();

        if (c=='A') Q[i].op=,addedge(Q[i].x,Q[i].y),addedge(Q[i].y,Q[i].x);else Q[i].op=;

    }

    for (int i=;i<=n;i++)

    if (!dfn[i]) dfs(i);

    cnt=;

    for (int i=;i<=n;i++)

    add(root[i],,n,dfn[i]);

    for (int i=;i<=q;i++)

    {

        if (dfn[Q[i].x]>dfn[Q[i].y]) swap(Q[i].x,Q[i].y);

        int p=find(Q[i].x);

        if (Q[i].op==)

        {

            fa[Q[i].y]=p;

            root[p]=merge(root[p],root[Q[i].y],,n);

        }

        else

        {

            int s=query(root[p],,n,dfn[Q[i].y],dfn[Q[i].y]+size[Q[i].y]-),t=tree[root[p]].x;

            printf("%lld\n",1ll*s*(t-s));

        }

    }

    fclose(stdin);fclose(stdout);

    return ;

}

相关文章