学长小清新题表之UOJ 14.DZY Loves Graph
题目描述
\(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\)。
输入格式
第一行两个正整数 \(n,m\)。表示有 \(n\) 个点 $m $个操作。 接下来 \(m\)行每行描述一个操作。
输出格式
对于每一个操作输出一行一个整数表示当前最小生成树边权和。
样例一
input
2 2
Add 1 2
Return
output
1
0
样例二
input
5 10
Add 2 1
Add 3 2
Add 4 2
Add 5 2
Add 2 3
Return
Delete 1
Add 2 3
Add 5 2
Return
output
0
0
0
10
10
10
0
0
15
0
样例三
见样例数据下载
限制与约定
| 测试点编号 | n | m | 其他 |
|---|---|---|---|
| \(1、2、3\) | \(n≤10^3\) | \(m≤10^3\) | 只有\(Add\)操作 |
| \(4\) | \(n≤2×10^5\) | \(m≤2×10^5\) | 只有\(Add\)操作 |
| \(5\) | \(n≤3×10^5\) | \(m≤5×10^5\) | |
| \(6\) | \(n≤2×10^5\) | \(m≤2×10^5\) | 没有\(Return\)操作 |
| \(7\) | \(n≤3×10^5\) | \(m≤5×10^5\) | |
| \(8\) | \(n≤2×10^5\) | \(m≤2×10^5\) | |
| \(9、10\) | \(n≤3×10^5\) | \(m≤5×10^5\) |
时间限制：\(1s\)
空间限制：\(64MB\)
分析
我们认真分析题目的话，不难得出以下结论
\(1\)、此题的空间限制较小，如果用可持久化数据 结构很可能会超空间
\(2\)、边权是从小到大加入的，因此如果之前加的边已经可以生成一棵树，那么之后加的边不会产生影响
\(3\)、题目中没有要求强制在线，而且有\(Return\)操作，可以考虑离线
对于\(Add\)操作，我们可以像最小生成树用并查集维护
如果当前的两个节点已经处于一个联通块，那么它们之间的权值一定小于新加入的权值，我们不去管他
如果两个节点属于一个联通块，我们就把两个节点并在一起
对于\(Delete\)操作，路径压缩并查集是无法解决的，因为它会打乱原来的结果，所以我们要用到按秩合并的并查集
所谓按秩合并，就是把深度小的并到深度大的上面或者是把子树小的并到子树大的上面
对于\(Return\)操作，因为是离线处理，所以就好办多了
如果撤销加边操作的话，我们把撤销操作改为删边操作即可
如果撤销删除操作，我们就不去删边，而是用一个\(ans\)数组去记录有\(k\)条边时的最小生成树的权值
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
typedef long long ll;//不开long long见祖宗
inline ll read(){
register ll x=0,f=1;
char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1LL)+(x<<3LL)+(ch^48);
ch=getchar();
}
return x*f;
}//快读卡常
struct asd{
char jls[3];
ll jla,jlb;
}b[maxn];//离线用结构体
ll fa[maxn],rk[maxn],shuyu[maxn],sta[maxn],top;
ll ans[maxn],n,m,tot,cnt,anscnt;
//fa:并查集父亲节点，rk:子树大小,shuyu:记录某条边属于哪一个节点,sta:存储使用过的边
//ans:记录边数为k时最小生成树的权值和,tot:记录最小生成树的权值,cnt:记录最小生成树的边数,anscnt:记录统计过的答案的个数
ll zhao(ll xx){
if(xx==fa[xx]) return xx;
return zhao(fa[xx]);
}//找到祖先节点
void bing(ll xx,ll yy,ll w){
ll aa=zhao(xx),bb=zhao(yy);
if(aa==bb){
shuyu[w]=-1;
return;
}
if(rk[aa]<rk[bb]) swap(aa,bb);
rk[aa]+=rk[bb];
fa[bb]=aa;
shuyu[w]=bb;
tot+=w,cnt++;
}//按秩合并
void shanchu(ll val){
ll xx=shuyu[val];
ll yy=fa[xx];
rk[yy]-=rk[xx];
fa[xx]=xx;
cnt--,tot-=val;
}//删边
int main(){
n=read(),m=read();
for(ll i=1;i<=n;i++){
fa[i]=i,rk[i]=1;
}
for(ll i=1;i<=m;i++){
scanf("%s",b[i].jls);
if(b[i].jls[0]=='A'){
b[i].jla=read(),b[i].jlb=read();
} else if(b[i].jls[0]=='D'){
b[i].jla=read();
}
}
//初始化+读入
for(ll i=1;i<=m;i++){
if(b[i].jls[0]=='A'){
bing(b[i].jla,b[i].jlb,i);
sta[++top]=i;
if(cnt<n-1) ans[++anscnt]=0;
else ans[++anscnt]=tot;
if(b[i+1].jls[0]=='R'){
b[i+1].jls[0]='D';
b[i+1].jla=1;
}
printf("%lld\n",ans[anscnt]);
} else if(b[i].jls[0]=='D'){
if(b[i+1].jls[0]=='R'){
printf("%lld\n%lld\n",ans[anscnt-b[i].jla],ans[anscnt]);
continue;
}
while(b[i].jla--){
ll now=sta[top--];
anscnt--;
if(shuyu[now]!=-1){
shanchu(now);
}
}
if(cnt<n-1) ans[anscnt]=0;
else ans[anscnt]=tot;
printf("%lld\n",ans[anscnt]);
}
}
return 0;
}