Konrad and Company Evaluation

F. Konrad and Company Evaluation

Reference: [codeforces 1230F]Konrad and Company Evaluation-violence

Thinking: For the analysis of the question, please refer to the reference blog. Because what you want is the number of triples, it is saved as a directed graph when saving, so that employees with lower salaries point to employees with higher salaries. Then when seeking triples, you only need to use triples The employee in the middle can be used as a reference point to solve the problem.

ll cal(int i){ return (cnt[i]-g[i].size())*g[i].size();}

Then when performing operations, because n is added every time, it must be larger than the two points connected between it, so for the point pointed to by this point, The formed triples will be recalculated, so first subtract the previously calculated part, and then add the new part.

Code:

// Created by CAD on 2019/10/1.#include #define ll long longusing namespace std;const int maxn=1e6+5;int cnt[maxn];vector g[maxn];ll cal(int i){ return (cnt[i]-g[i].size()) *g[i].size();}int main(){ ios::sync_with_stdio(false); cin.tie(0); int n,m; cin>>n>>m; for(int i=1 ,u,v;i<=m;++i) {cin>>u>>v; if(u>v) swap(u,v); g[u].push_back(v); cnt[u] ++,cnt[v]++;} ll ans=0; for(int i=1;i<=n;++i) ans+=cal(i); int q; cin>>q; cout<< ans<>x; ans-=cal(x); for(auto i:g[x]) {ans-=cal(i); g[i ].push_back(x); ans+=cal(i); g[x].clear();} cout<