Codeforces 1229C. Konrad and Company Evaluation

传送门

首先考虑如何算出答案，考虑枚举中间那个点，显然每个点作为中间的点的次数为入度乘出度

所以答案就是每个点的入度乘出度之和

然后每个点开一个 $vector$ 维护从它出去的点数，每次修改的时候直接暴力改出度然后暴力删边并加入新边

这样可以证明复杂度是对的，这里有两种证明，其中第二种是来自官方题解

证明 $1$ ：

不妨让值小的点指向值更大的点

首先对于所有出度小于根号 $m$ 的点，单次暴力复杂度显然小于 $\sqrt {m}$，那么总复杂度不超过 $q \sqrt {m}$

对于出度大于根号 $m$ 的点 $x$，考虑把初始所有点 $1$ 到 $n$ 再加上所有的修改操作连在后面，排成一排看成一个数组

从 $n+1$ 开始从左到右枚举数组，一旦枚举到位置 $i$ 为 $x$ 意思就是这里修改了一次 $x$，设 $x$ 上一次出现的位置为 $las$

那么显然只有数组里 $las+1$ 到 $i$ 的点的如果和 $x$ 有边，那么才会产生 $1$ 代价，因为所有的 $[las+1,i]$ 在数组里排成了连续的一排

（就是 $[1,5],[6,10],[11,30]...$这样的），所以对于节点 $x$ 最终均摊复杂度最多就是 $O(n)$ 的

又因为出度大于 $\sqrt {m}$ 的点不会超过 $\sqrt {m}$ 个，所以对于出度大于 $\sqrt {m}$ 的点，总的复杂度也不超过 $n \sqrt {m}$

那么综合一下得到总复杂度就是 $n \sqrt {n}$ （这里 $n,m,q$ 同阶）

证明 $2$：

不妨让值小的点指向值更大的点

考虑把图中的节点按照度数从大到小排成一排（注意这里是度数不是出度，所以之后图不会改变）

那么首先对于每个节点 $x$ ，$x$ 左边的并且和 $x$ 有边相连的点不超过 $\sqrt {2m}$

因为如果超过 $\sqrt {2m}$ ，那么首先 $x$ 的度数就超过 $\sqrt {2m}$ 并且左边点数也大于等于 $\sqrt {2m}$，又因为左边的点度数都比 $x$ 大

那么总度数显然超过 $2m$ ，所以这种情况一定不可能出现

定义一张图的势能为图中所有点指向右边的点的边的数量，首先初始图的势能最大为 $m$

由之前的证明可以得到每次操作完一个点 $x$ 以后，$x$ 的左边最多有 $\sqrt {2m}$ 条边变成指向右边，并且剩下的边（ $x$ 指向右边的边）都变成指向左边，所以每一次操作最多使图的势能增加 $\sqrt {2m}$ ，那么最终增加的势能的总和最多为 $m+q\sqrt {2m}$

那么首先把边从指向左边翻转到指向右边（即增加势能）最多就为 $m+q\sqrt {2m}$

又发现如果我们要把边从指向右边变成指向左边，那么就一定要消耗图中的势能，又因为势能总增加量最多为 $m+q\sqrt {2m}$ 所以最多消耗的势能也就是 $m+q\sqrt {2m}$

所以翻转边的总复杂度为 $O(m+q\sqrt {2m})$

证明完毕

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<vector>

using namespace std;

typedef long long ll;

inline int read()

{

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

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

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int N=2e5+;

int n,m,du[N],out[N];

ll Ans;

vector <int> V[N];

inline ll calc(int i) { return 1ll*out[i]*(du[i]-out[i]); }

int main()

{

    n=read(),m=read(); int a,b;

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

    {

        a=read(),b=read(),du[a]++,du[b]++;

        if(a>b) swap(a,b);

        V[a].push_back(b); out[a]++;

    }

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

    printf("%lld\n",Ans);

    int Q=read();

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

    {

        a=read(); int len=V[a].size();

        for(int j=;j<=len;j++)

        {

            b=V[a][len-j]; V[a].pop_back();

            V[b].push_back(a);

            Ans-=calc(a)+calc(b);

            out[a]--; out[b]++;

            Ans+=calc(a)+calc(b);

        }

        printf("%lld\n",Ans);

    }

    return ;

}

巴特西

Codeforces 1229C. Konrad and Company Evaluation

最新文章

热门文章