题意：有i个人，m对两两之间的关系，第i个人初始的薪水为i，有q次操作，第i次操作会把v[i]号的薪水提升成n+i
如果两个人之间存在关系，薪水高的会向薪水低的炫耀
定义u,v,w为一个三元组，当u向v炫耀，v向w炫耀
要求每次操作后输出当前三元组个数
n,m,q<=1e5
思路：将人看成点，关系看成边，定义方向为从小到大
显然每次操作后被操作的人的薪水都会变成最大的，等价于将它的所有出边变成入边
答案即为所有点的入度*出度之和
vector暴力维护出边
学习了一下杜教的写法
势能分析见https://blog.csdn.net/Izumi_Hanako/article/details/101267502
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 typedef unsigned int uint; 5 typedef unsigned long long ull; 6 typedef pair<int,int> PII; 7 typedef pair<ll,ll> Pll; 8 typedef vector<int> VI; 9 typedef vector<PII> VII; 10 typedef pair<ll,ll>P; 11 #define N 200010 12 #define M 200010 13 #define fi first 14 #define se second 15 #define MP make_pair 16 #define pi acos(-1) 17 #define mem(a,b) memset(a,b,sizeof(a)) 18 #define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++) 19 #define per(i,a,b) for(int i=(int)a;i>=(int)b;i--) 20 #define lowbit(x) x&(-x) 21 #define Rand (rand()*(1<<16)+rand()) 22 #define id(x) ((x)<=B?(x):m-n/(x)+1) 23 #define ls p<<1 24 #define rs p<<1|1 25 26 const ll MOD=1e9+7,inv2=(MOD+1)/2; 27 double eps=1e-4; 28 int INF=1<<30; 29 ll inf=5e13; 30 int dx[4]={-1,1,0,0}; 31 int dy[4]={0,0,-1,1}; 32 33 vector<int> c[N]; 34 int d[N]; 35 36 int read() 37 { 38 int v=0,f=1; 39 char c=getchar(); 40 while(c<48||57<c) {if(c=='-') f=-1; c=getchar();} 41 while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar(); 42 return v*f; 43 } 44 45 ll calc(int i) 46 { 47 int t=(int)c[i].size(); 48 return 1ll*t*(d[i]-t); 49 } 50 51 int main() 52 { 53 int n=read(),m=read(); 54 rep(i,1,m) 55 { 56 int x=read(),y=read(); 57 if(x>y) swap(x,y); 58 c[x].push_back(y); 59 d[x]++; d[y]++; 60 } 61 ll ans=0; 62 rep(i,1,n) ans+=calc(i); 63 printf("%I64d ",ans); 64 int q=read(); 65 rep(i,1,q) 66 { 67 int u=read(); 68 ans-=calc(u); 69 for(int j=0;j<c[u].size();j++) 70 { 71 int v=c[u][j]; 72 ans-=calc(v); 73 c[v].push_back(u); 74 ans+=calc(v); 75 } 76 c[u].clear(); 77 printf("%I64d ",ans); 78 } 79 80 81 82 return 0; 83 }