[BJOI2014]大融合

C++14(g++5.4) 解法, 执行用时: 155ms, 内存消耗: 55320K, 提交时间: 2020-01-20 13:48:21

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MX=1e5+9;

int fa[MX];
int fin(int x){
    if( fa[x]==x )
        return x;
    else
        return fa[x]=fin(fa[x]);
}

struct node{
    int x,y;
    int op;
}q[MX];

struct NNode{
    int to;
    int next;
}edge[MX<<1];
int head[MX],tot=0;

void add(int u,int v){
    edge[tot].next=head[u];
    edge[tot].to=v;
    head[u]=tot++;
}

struct Node{
    int l;
    int r;
    int siz=0;
}t[MX*40];
int root[MX],st[MX],ed[MX],de[MX];
int cnt=0,n,T;

void build(int &k,int l,int r,int pos){
    if( !k )
        k=++tot;
    if( l==r ){
        t[k].siz=1;
        return ;
    }
    int mid=(l+r)>>1;
    if( pos<=mid )
        build(t[k].l,l,mid,pos);
    else
        build(t[k].r,mid+1,r,pos);
    t[k].siz=t[t[k].l].siz+t[t[k].r].siz;
}

int merge(int x,int y){
    if( !x ) return y;
    if( !y ) return x;
    t[x].siz+=t[y].siz;
    t[x].l=merge(t[x].l,t[y].l);
    t[x].r=merge(t[x].r,t[y].r);
    return x;
}

int vis[MX];
void dfs(int u,int f,int deth){
    vis[u]=1;
    st[u]=++cnt;
    de[u]=deth;
    build(root[u],1,n,st[u]);
    for( int i=head[u] ; ~i ; i=edge[i].next ){
        int to=edge[i].to;
        if( to!=f )
            dfs(to,u,deth+1);
    }
    ed[u]=cnt;
}

char s[20];

int que( int k,int l,int r,int L,int R){
    if( !k )
        return 0;
    if( L<=l && r<=R )
        return t[k].siz;
    int mid=(l+r)>>1,ans=0;
    if( L<=mid )
        ans+=que(t[k].l,l,mid,L,R);
    if( mid<R )
        ans+=que(t[k].r,mid+1,r,L,R);
    return ans;
}

int main()
{
    //freopen("input.txt","r",stdin);
    memset(head,-1,sizeof(head));
    memset(vis,0,sizeof(vis));
    scanf("%d %d",&n,&T);
    int x,y;
    for( int i=1 ; i<=T ; i++ ){
        scanf("%s",s);
        scanf("%d %d",&x,&y);
        if( s[0]=='A' ) add(x,y),add(y,x);
        if( s[0]=='A' ) q[i].op=0,q[i].x=x,q[i].y=y;
        if( s[0]=='Q' ) q[i].op=1,q[i].x=x,q[i].y=y;
    }
    tot=0,cnt=0;
    for( int i=1 ; i<=n ; i++ ){
        if( !vis[i] )
            dfs(i,0,0);
        fa[i]=i;
    }
    for( int i=1 ; i<=T ; i++ ){
        x=q[i].x,y=q[i].y;
        if( q[i].op==0 ){
            x=fin(x),y=fin(y);
            root[x]=merge(root[x],root[y]);
            fa[y]=x;
        }
        else{
            if( de[x]<de[y] )
                swap(x,y);
            int z=fin(x);
            int num=que(root[z],1,n,st[x],ed[x]);
            printf("%d\n",(t[root[z]].siz-num)*num);
        }
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 48ms, 内存消耗: 8288K, 提交时间: 2020-09-09 22:35:47

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e5+5;
struct node{int opt,u,v;}a[N];
struct Edge{int to,nxt;}e[N<<1];
int n,q,fst[N],tote,fa[N],dep[N],bf[N],L[N],R[N],c[N],dfn;bool vis[N];
void adde(int u,int v){e[++tote]=(Edge){v,fst[u]};fst[u]=tote;}
void dfs(int u,int f){
	vis[u]=true;L[u]=++dfn;fa[u]=f;dep[u]=dep[f]+1;
	for(int i=fst[u],v;i;i=e[i].nxt)if((v=e[i].to)!=f)dfs(v,u);
	R[u]=dfn;
}
int find(int u){return bf[u]==u?u:bf[u]=find(bf[u]);}
void change(int x,int y){for(int i=x;i<=n;i+=(i&-i))c[i]+=y;}
int ask(int l,int r){
	int res=0;
	for(int i=r;i;i-=(i&-i))res+=c[i];
	for(int i=l-1;i;i-=(i&-i))res-=c[i];
	return res;
}
int main(){
	scanf("%d%d",&n,&q);
	for(int i=1,u,v;i<=q;i++){
		char opt[5];scanf("%s",opt);scanf("%d%d",&u,&v);
		a[i].u=u;a[i].v=v;
		if(opt[0]=='A')a[i].opt=1,adde(u,v),adde(v,u);else a[i].opt=2;
	}
	for(int i=1;i<=n;i++){bf[i]=i;if(!vis[i])dfs(i,0);}
	for(int i=1;i<=n;i++){
		change(L[i],1);
		if(fa[i])change(L[fa[i]],-1);
	}
	for(int i=1,u,v,ru,rv;i<=q;i++){
		u=a[i].u;v=a[i].v;LL x,y;
		if(dep[u]>dep[v])swap(u,v);
		if(a[i].opt==1){
			ru=find(u);rv=find(v);bf[rv]=ru;
			x=ask(L[rv],R[rv]);change(L[u],x);
			if(fa[ru])change(L[fa[ru]],-x);
		}else{
			ru=find(u);x=ask(L[v],R[v]);y=ask(L[ru],R[ru]);
			printf("%lld\n",x*(y-x));
		}
	}
	return 0;
}

详情