UOJ小清新题表
题目内容
DZY开始有\(n\)个点，现在他对这\(n\)个点进行了\(m\)次操作，对于第\(i\)个操作（从\(1\)开始编号）有可能的三种情况：
Add a b： 表示在\(a\)与\(b\)之间连了一条长度为\(i\)的边（注意，\(i\)是操作编号）。保证\(1≤a,b≤n\)。
Delete k： 表示删除了当前图中边权最大的k条边。保证k一定不会比当前图中边的条数多。
Return： 表示撤销第$ i−1$次操作。保证第\(1\)次操作不是Return且第\(i−1\)次不是Return操作。
请你在每次操作后告诉DZY当前图的最小生成树边权和。如果最小生成树不存在则输出 0。
数据范围
\(1\leq n\leq 3\times 10^5,1\leq m\leq 5\times 10^5\)
思路
很好的一道题，顺便学了下按秩合并
先考虑没有Return的情况，那么只需考虑删边的情况。如果你要使用路径压缩的话删边会很麻烦，那么就用按秩合并的策略，没加入一条边将一直保持不变直至其被删除（没错，通俗点就是直接删了），操作次数为\(m\)，最多加入的边数也就只有\(O(m)\)而已。加上按秩合并每次操作\(\log n\)，总的时间效率是\(O(n\log n)\)。可以获得70分的部分分。
此时有神犇表示可持久化并查集！
注意看比赛题目，UOJ Easy Round，显然可持久化不星
所以实际上我们只需要采用离线的策略。当我们执行第\(i\)个操作的时候就可以知道第\(i+1\)的操作是否为Return操作。
对于当前为Add操作，你可以选择直接把Return改成Delete。
如果当前是Delete操作的话，我们可以事先存下还没有删除的时候的答案，直接一起输出即可。
时间效率\(O(n\log n)\)，期望得分 40 100。（如果你不像我一样犯nt错误的话）
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5e5+10;
int n,m,tot,kcnt;
int fa[maxn],siz[maxn],mem[maxn];
ll ans[maxn];//记录图中有i条边时的答案ans[i]
stack<int> sta;
struct Node{
char opt[5];
int x,y;
}q[maxn];
inline int read(){
int x=0,fopt=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')fopt=-1;
ch=getchar();
}
while(isdigit(ch)){
x=(x<<3)+(x<<1)+ch-48;
ch=getchar();
}
return x*fopt;
}
inline int Find(int x){
return x==fa[x]?x:Find(fa[x]);//别路径压缩了
}
inline void Merge(int x,int y,int w){
int fx=Find(x),fy=Find(y);
sta.push(w);
if(fx==fy)return mem[w]=-1,void();
if(siz[fx]>siz[fy])swap(fx,fy);
fa[fx]=fy;
/*while(fa[fy]!=fy){
siz[fy]+=siz[fx];
fy=fa[fy];
}*///如果你这么写就会获得40分的好成绩
while(1){
siz[fy]+=siz[fx];
fy=fa[fy];
if(fa[fy]==fy)break;
}//原因是一开始就连自己的情况没有往上跳而直接略过去了
mem[w]=fx;
}
inline void Del(int x){
int fx=fa[x];
while(fa[fx]!=fx){
siz[fx]-=siz[x];
fx=fa[fx];
}//由于删除的时候至少是两个点相连的所以这里没关系
fa[x]=x;
}
void Solve(){
ll res=0;
for(int i=1;i<=m;i++){
if(q[i].opt[0]=='A'){
Merge(q[i].x,q[i].y,i);
if(~mem[i])res+=i,kcnt++;
ans[++tot]=(kcnt<n-1)?0:res;
printf("%lld\n",ans[tot]);
if(q[i+1].opt[0]=='R'){
q[i+1].opt[0]='D';
q[i+1].x=1;
}
}else if(q[i].opt[0]=='D'){
if(q[i+1].opt[0]=='R'){
printf("%lld\n%lld\n",ans[tot-q[i].x],ans[tot]);
continue;//直接一次性输出两个就行了
}
while(q[i].x--){
int u=sta.top();
sta.pop();tot--;
if(mem[u]==-1)continue;
Del(mem[u]);
res-=u;kcnt--;
}
ans[tot]=(kcnt<n-1)?0:res;
printf("%lld\n",ans[tot]);
}
}
}
void Init(){
for(int i=1;i<=n;i++){
fa[i]=i;
siz[i]=1;
}
}
int main(){
n=read();m=read();
Init();
for(int i=1;i<=m;i++){
bool flag=0;
scanf("%s",q[i].opt);
if(q[i].opt[0]=='A')
q[i].x=read(),q[i].y=read();
else if(q[i].opt[0]=='D')
q[i].x=read();
}
Solve();
return 0;
}
关于代码高亮，他好像SPFA了他好了