感觉做得有点复杂了，但是AC了还是。。。爽。。。
题意：给你n个点每个点有一个价值，接下来有m条边，然后是q个操作，每个操作有三种情况：
F X K：寻找与X点直接或间接相连的不小于价值K的最小价值，如果找不到就是0
U X K：将X点价值变为K
E A B：删除点A与点B形成的边
最后求价值总和的平均值
首先我们看F操作和U操作可以使用map解决，因为这是典型的带修改并区间找寻大于等于某值的最小值。然后我们看删边，如果直接删的话，我们需要遍历这一维map然后拆分，时间过不了。因此我们想到使用离线操作倒序添边，然后处理集合合并问题就是并查集的典型题了。
接着我们离线后要把每个E与U都处理后再添边，对于U我们必须保存所有修改的历史，因此使用vector。而m条边中删除E的边，我们需要节约时间。存下总所有边与需要删除的边，然后一起排序后双指针维护添边（因为需要删除的边一定在所有边中出现过，且没有重边）。接着对于维护E，添边后需要把一个父节点并上去，且两个map也要合并，因此我们为了节约合并时间，需要简单的启发式合并。其实就是并查集合并时把个数少的并到个数多的上面。
#include<set> #include<map> #include<queue> #include<stack> #include<cmath> #include<vector> #include<string> #include<cstdio> #include<cstring> #include<stdlib.h> #include<iostream> #include<algorithm> using namespace std; #define eps 1E-8 /*注意可能会有输出-0.000*/ #define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型 #define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化 #define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0 #define mul(a,b) (a<<b) #define dir(a,b) (a>>b) typedef long long ll; typedef unsigned long long ull; const int Inf=1<<28; const double Pi=acos(-1.0); const int Mod=1e9+7; const int Max=300010; struct node { char typ[2]; int u,v; }add[Max],del[Max],ope[Max]; int fat[Max],ran[Max];//离线添边的并查集 map<int,int> mp[Max];//祖先形成的集合里的元素 vector<int> vec[Max];//存下修改的过程值 int len[Max]; void Init(int n) { for(int i=0;i<n;++i) { ran[i]=1; len[i]=0; vec[i].clear(); mp[i].clear(); fat[i]=i; } return; } int Find(int x) { if(x==fat[x]) return fat[x]; return fat[x]=Find(fat[x]); } void UnMap(int x1,int y1) { for(map<int,int>::iterator it=mp[x1].begin();it!=mp[x1].end();) { if(!mp[y1].count(it->first)) mp[y1][it->first]=it->second; else mp[y1][it->first]+=it->second; mp[x1].erase(it++);//删除 } return; } void Union(int x,int y) { int x1=Find(x); int y1=Find(y); if(x1==y1) return; if(ran[x1]<ran[y1]) { fat[x1]=y1;//价值合并 ran[y1]+=ran[x1]; UnMap(x1,y1); } else { fat[y1]=x1;//价值合并 ran[x1]+=ran[y1]; UnMap(y1,x1); } return; } bool cmp(struct node p1,struct node p2) { if(p1.u==p2.u) return p1.v<p2.v; return p1.u<p2.u; } map<int,int>::iterator it; double Solve(int n,int m,int q,int cnt,int dig) { int coun=0; double ans=0.0; for(int i=0;i<n;++i) mp[i][vec[i][len[i]]]=1;//开始每个集合是自己 sort(add,add+m,cmp); sort(del,del+cnt,cmp); del[cnt].u=del[cnt].v=-1; //for(int i=0;i<m;++i) // printf("%d %d ",add[i].u,add[i].v); // printf("OK "); // for(int i=0;i<cnt;++i) //printf("%d %d ",del[i].u,del[i].v); for(int i=0;i<m;++i)//初始添边 { if(add[i].u==del[coun].u&&add[i].v==del[coun].v)//两边排序后双指针维护 coun++; else {//printf("OK "); Union(add[i].u,add[i].v); } } for(int i=q-1;i>=0;--i) { if(ope[i].typ[0]=='F') { int x1=Find(ope[i].u); it=mp[x1].lower_bound(ope[i].v); if(it==mp[x1].end()) ans+=0.0; else ans+=it->first; } else if(ope[i].typ[0]=='E') Union(ope[i].u,ope[i].v); else//换价值 { int x1=Find(ope[i].u); mp[x1][ope[i].v]--; if(mp[x1][ope[i].v]==0) mp[x1].erase(ope[i].v); if(mp[x1].count(vec[ope[i].u][len[ope[i].u]-1])) mp[x1][vec[ope[i].u][--len[ope[i].u]]]++; else mp[x1][vec[ope[i].u][--len[ope[i].u]]]=1; } }//printf("%d ",dig); return ans/dig; } int main() { int n,m,q; int u,v,c; int cnt,dig,coun=0; while(~scanf("%d %d %d",&n,&m,&q)) { Init(n); dig=cnt=0; for(int i=0;i<n;++i) { scanf("%d",&c); vec[i].push_back(c); } for(int i=0;i<m;++i) { scanf("%d %d",&u,&v); u--,v--; if(u>v) swap(u,v); add[i].u=u; add[i].v=v; } for(int i=0;i<q;++i) { scanf("%s %d %d",&ope[i].typ,&ope[i].u,&ope[i].v); if(ope[i].typ[0]=='F') { dig++; ope[i].u--; } else if(ope[i].typ[0]=='E') { ope[i].u--,ope[i].v--; if(ope[i].u>ope[i].v) swap(ope[i].u,ope[i].v); del[cnt].u=ope[i].u,del[cnt++].v=ope[i].v; } else { ope[i].u--; len[ope[i].u]++; vec[ope[i].u].push_back(ope[i].v); } } printf("Case %d: %.3f ",++coun,Solve(n,m,q,cnt,dig)); Init(n); } return 0; }