题解 P7220 【[JOISC2020] ジョイッターで友だちをつくろう】

周子衡 · 2021-03-29 17:19:00 · 题解

考虑维护最后图中极大团，也就是所有的点集 S，满足对于 S 中的任意两点 u,v，在举办活动后既有 u\rightarrow v 的边，也有 v\rightarrow u 的边。我们先来分析一下一个大小为 s 的极大团给答案带来的贡献：

• 极大团内部有 s(s-1) 条边；
• 对于每个向该团中连了至少一条边的团外的点，该点最后会和团中所有人连单向边。因而如果该团被 k 个点连向，将会给答案带来 sk 的贡献。注意：这里的 k 是连向该团的不同点数，不是连向该团的团数。

我们考虑在加边过程中，用并查集维护每个极大团，并对每个极大团 S，动态维护集合：

当每次加入边 x\rightarrow y 时，设 x 在团 X 中，y 在团 Y 中，如果 Y 之前向 X 连过边，那么我们需要把 X,Y 合并。为了确保时间复杂度，采用启发式合并的技巧。注意一次合并可能会引起其他的合并，使用队列来维护所有的合并即可。如果 Y 之前未向 X 连过边，我们简单地更新即可。注意要去掉集合中的重复元素，可以采用 std::set 实现。总时间复杂度 O(m\log^2 m)。

#include<cstdio>
#include<set>
#include<queue>

using namespace std;

struct BCJ
{
    int fa[200000];
    void init(int n){for(int i=1;i<=n;i++)fa[i]=i;}
    int fnd(int x){return x==fa[x]?x:fa[x]=fnd(fa[x]);}
}B;

set<int> IN[200000],OUT[200000],IP[200000],S[200000];
queue<pair<int,int> > Q;

long long calc(int x){return (long long)(S[x].size()-1)*S[x].size()+(long long)IP[x].size()*S[x].size();}
long long ans;

typedef set<int>::iterator IT;

void merge(int x,int y)
{
    x=B.fnd(x),y=B.fnd(y);if(x==y)return;
    if(S[x].size()<S[y].size())swap(x,y);
    B.fa[y]=x;
    ans-=calc(x),ans-=calc(y);
    if(IN[x].count(y))IN[x].erase(y);
    if(OUT[x].count(y))OUT[x].erase(y);
    for(IT it=S[y].begin();it!=S[y].end();it++)
    {
        int u=*it;S[x].insert(u);
        if(IP[x].count(u))IP[x].erase(u);
    }
    for(IT it=IP[y].begin();it!=IP[y].end();it++)
    {
        int u=*it;if(!IP[x].count(u)&&!S[x].count(u))IP[x].insert(u);
    }
    for(IT it=IN[y].begin();it!=IN[y].end();it++)
    {
        int u=*it;if(u==x)continue;
        OUT[u].erase(y),OUT[u].insert(x);IN[x].insert(u);
        if(OUT[x].count(u))Q.push(make_pair(x,u));
    }
    for(IT it=OUT[y].begin();it!=OUT[y].end();it++)
    {
        int u=*it;if(u==x)continue;
        IN[u].erase(y),IN[u].insert(x);OUT[x].insert(u);
        if(IN[x].count(u))Q.push(make_pair(x,u));
    }
    ans+=calc(x);
}
void work()
{
    while(!Q.empty())
    {
        int x=Q.front().first,y=Q.front().second;Q.pop();
        merge(x,y);
    }
}

int main()
{
    int n=0,m=0;scanf("%d%d",&n,&m);B.init(n);
    for(int i=1;i<=n;i++)S[i].insert(i);
    for(int i=1;i<=m;i++)
    {
        int x=0,y=0;scanf("%d%d",&x,&y);
        int fx=B.fnd(x),fy=B.fnd(y);if(fx==fy){printf("%lld\n",ans);continue;}
        if(IN[fx].count(fy))
        {
            Q.push(make_pair(fx,fy));work();
        }
        else
        {
            ans-=calc(fx),ans-=calc(fy);
            IN[fy].insert(fx),IP[fy].insert(x),OUT[fx].insert(fy);
            ans+=calc(fx),ans+=calc(fy);
        }
        printf("%lld\n",ans);
    }
}