Codeforces 1210 D Konrad and Company Evaluation —— 暴力

This way

题意：

现在有n个人，第i个人的工资一开始是i，现在有一些人相互讨厌，然后如果第x个人和第y个人相互讨厌，并且x的工资比y高，那么x就会向y炫耀。
x,y,z这三个人的组合是危险的，当x会向y炫耀，y会向z炫耀。
每次修改一个人的工资为大于所有人，并且询问你此时有多少种三人组合是危险的

题解：

那么这道题就有一个很暴力的做法，我们通过样例解释可以发现，其实就是一张有向图，然后答案是每个点的入度*出度。之后的话就是修改每个点的入边为出边。如果每次输入暴力修改每个点的入边为出边的话，乍一看是 O ( n 2 ) O(n^2) O(n2)的，但是仔细思考可以发现，每一条边只连接了2个人，并且它会翻转当且仅当修改的是被指向的那个人。
也就是说，如果修改一个人的值会翻转n条边，那么只有在接下来修改n个人的值才能将所有边翻转回来。
所以我断定暴力修改的时间复杂度是O(n)的，然后用vector维护每条边的反边，在删除的时候是O(log)的，所以总的时间复杂度是 O ( n l o g n ) O(nlogn) O(nlogn)的。如果用map维护的话，时间复杂度是 O ( n ∗ q ∗ l o g n ) O(n*q*logn) O(n∗q∗logn)

最终时间复杂度：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+5;
vector<int>mp[N];
int in[N],out[N];
int main()
{
    int n,m,x,y;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        if(x>y)swap(x,y);
        mp[x].push_back(y),in[x]++,out[y]++;
    }
    ll ans=0;
    for(int i=1;i<=n;i++)
        ans+=1ll*in[i]*out[i];
    printf("%lld\n",ans);
    int q;
    scanf("%d",&q);
    while(q--){
        scanf("%d",&x);
        ans-=1ll*in[x]*out[x];
        for(auto i:mp[x]){
            mp[i].push_back(x);
            ans+=1ll*(in[i]+1)*(out[i]-1)-1ll*in[i]*out[i];
            in[x]--,out[x]++,in[i]++,out[i]--;
        }
        mp[x].clear();
        printf("%lld\n",ans);
    }
    return 0;
}