首页 > 其他 > 详细

BZOJ4530 BJOI2014大融合(线段树合并+并查集)

时间:2018-07-29 16:04:12      阅读:180      评论:0      收藏:0      [点我收藏+]

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

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

#include<iostream> 
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int read()
{
    int x=0,f=1;char c=getchar();
    while (c<0||c>9) {if (c==-) f=-1;c=getchar();}
    while (c>=0&&c<=9) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x*f;
}
#define N 100010
int n,q,fa[N],dfn[N],p[N],root[N],size[N],t=0,cnt=0;
struct data{int x,y,op;
}Q[N];
struct data2{int to,nxt;
}edge[N<<1];
struct data3{int l,r,x;
}tree[N<<6];
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]=1;
    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>>1;
    if (x<=mid) add(tree[k].l,l,mid,x);
    else add(tree[k].r,mid+1,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>>1;
    tree[x].l=merge(tree[x].l,tree[y].l,l,mid),
    tree[x].r=merge(tree[x].r,tree[y].r,mid+1,r);
    return x;
}
int query(int k,int l,int r,int x,int y)
{
    if (!k) return 0;
    if (l==x&&r==y) return tree[k].x;
    int mid=l+r>>1;
    if (y<=mid) return query(tree[k].l,l,mid,x,y);
    else if (x>mid) return query(tree[k].r,mid+1,r,x,y);
    else return query(tree[k].l,l,mid,x,mid)+query(tree[k].r,mid+1,r,mid+1,y);
}
int main()
{
    freopen("bzoj4530.in","r",stdin);
    freopen("bzoj4530.out","w",stdout);
    n=read(),q=read();
    for (int i=1;i<=n;i++) fa[i]=i;
    for (int i=1;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=0,addedge(Q[i].x,Q[i].y),addedge(Q[i].y,Q[i].x);else Q[i].op=1;
    }
    for (int i=1;i<=n;i++) 
    if (!dfn[i]) dfs(i);
    cnt=0;
    for (int i=1;i<=n;i++)
    add(root[i],1,n,dfn[i]);
    for (int i=1;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==0)
        {
            fa[Q[i].y]=p;
            root[p]=merge(root[p],root[Q[i].y],1,n);
        }
        else 
        {
            int s=query(root[p],1,n,dfn[Q[i].y],dfn[Q[i].y]+size[Q[i].y]-1),t=tree[root[p]].x;
            printf("%lld\n",1ll*s*(t-s));
        }
    }
    fclose(stdin);fclose(stdout);
    return 0;
}

 

BZOJ4530 BJOI2014大融合(线段树合并+并查集)

原文:https://www.cnblogs.com/Gloid/p/9385412.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!