【YER #1】城市建设
有 \(n\) 个城市，每个城市有一个权重 \(w_i\)。每天会新修一条铁路，连接两个城市。定义某天的“交通量” \(=\) 所有能互相到达的城市对的 \(w_i×w_j\) 之和。
给你 \(q\) 个询问，问第 \(t\) 天的交通量。
考场上面没注意写错了一个地方，导致复杂度炸了100->50pts，非常愤怒。
很容易想到每一次修铁路用并查集维护联通块，发现只有修完铁路答案才有变化，那就把修完这条铁路的答案记下来，最后询问时二分找到在询问时间前修建的铁路的答案即可。
/*
先把铁路修建按时间排序，枚举m个时间点t，保存此时的答案
我们枚举点，计算以这个点为根的连通块的贡献，容易发现(w1+w2+...+wn)^2-(w1^2-w2^2...)=2(w1w2+w1w3+w1w4......)
询问时对于t，找到铁路修建时间x,y，使得x<=t<y，给出保存过的x时间时的答案
*/#include<bits/stdc++.h>
using namespace std;
#define int long long
int w[100010];
struct node{int t,a,b;
}a[100010];
bool cmp(node a,node b) {return a.t<b.t;
}
int tt[100010],cnt;
int fa[100010],sum[100010],sum2[100010],ans[100010];
int find(int x) {if(fa[x]==x) return x;return fa[x]=find(fa[x]);
}
int tmp;
void join(int a,int b) {int aa=find(a),bb=find(b);if(aa!=bb) {tmp-=(sum[aa]*sum[aa]-sum2[aa])/2;//把原来的去掉 tmp-=(sum[bb]*sum[bb]-sum2[bb])/2;fa[bb]=aa;sum[aa]+=sum[bb];sum2[aa]+=sum2[bb];tmp+=(sum[aa]*sum[aa]-sum2[aa])/2;}
}
signed main() {ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);int n,m,q;cin>>n>>m>>q;for(int i=1;i<=n;i++) {cin>>w[i];}for(int i=1;i<=m;i++) {cin>>a[i].t>>a[i].a>>a[i].b;}sort(a+1,a+1+m,cmp);
// for(int i=1;i<=m;i++) {
// cout<<a[i].t<<"\n";
// }for(int i=1;i<=m;i++) {if(a[i].t!=a[i-1].t) {tt[++cnt]=a[i].t;}}for(int i=1;i<=n;i++) {fa[i]=i;sum[i]=w[i];sum2[i]=w[i]*w[i];}int last=1;//不要重复join! 100->50!!! for(int i=1;i<=cnt;i++) {for(int j=last;j<=m&&a[j].t<=tt[i];j++) {join(a[j].a,a[j].b);last=j;}ans[i]=tmp;}while(q--) {int t;cin>>t;int l=1,r=cnt,pos=0;while(l<=r) {int mid=(l+r)>>1;if(tt[mid]<=t) {pos=mid;l=mid+1;}else r=mid-1;}cout<<ans[pos]<<"\n";}return 0;
}