来,看题
思考
显然是并查集。暴力的方法很显然:每一步修改时遍历所有点,找出在该并查集内的点并修改权值,时间复杂度过高,会TLE
改进1 ————懒惰标记
对于一个并查集,如果此并查集并没有改动(没有新点加入该并查集),那么没有必要每次进行修改操作时都老老实实的修改。我们可以创建一个数组tag[i]用于表示第i个点为根的并查集应该被修改的值。在进行修改操作时增加tag[]中的值,而当进行并查集合并操作时(即1操作)时判断tag[]是否为0,不为0再遍历,可大大节约时间。当然在所有操作结束后tag数组可能不为0,还需要用同样的方式再更新一次权值。
改进2———— 链表
每次都枚举n个点的代价太大了,我们需要一种快速的操作。如果我们能在更改完并查集的根的权值时无缝衔接到并查集的每个子节点并更改其权值,即可省去漫长的遍历,时间将会更快。考虑使用单向链表来实现无缝衔接的过程。
struct NODE{
//int perv;前驱节点,这道题中没有用
int next;//表示该节点的下一个节点是什么(便于无缝衔接)
int lastson;//表示以该节点为并查集的根的最后一个节点是什么(便于合并)
long long val;
}node[10004];
这样我们在传递懒惰标记的过程中就可以顺着next更新权值。
lastson的作用十分重要:
int getf(int x)
{
if(x==fa[x])return fa[x];
return fa[x]=getf(fa[x]);
}
void merge(int a,int b)
{
int x=getf(a);
int y=getf(b);
if(x!=y)
{
fa[x]=y;
//node[a].prev=node[y].lastson;
node[node[y].lastson].next=x;
node[y].lastson=node[x].lastson;
}
}
在merge的过程中,由于我们令fa[x]=y,那么x需要接到y的最后一个子节点的后面,此时lastson就派上用场了,我们将y的lastson的后继节点改为x,而此时y的lastson在合并后发生了改变,变成了原来x的lastson(请大家仔细回味,如果理解不透彻可以画图辅助),由此我们将y的lastson更改为原来x的lastson,而x的lastson不用管,他在以后的链表搭建过程中不会用到。
正如fa[i]一样,lastson[i]也应在进行操作前被初始化为i。
完整代码如下:
#include<bits/stdc++.h>
using namespace std;
int tag[10004],fa[10004];
struct NODE{
//int perv;
int next;
int lastson;
long long val;
}node[10004];
int getf(int x)
{
if(x==fa[x])return fa[x];
return fa[x]=getf(fa[x]);
}
void merge(int a,int b)
{
int x=getf(a);
int y=getf(b);
if(x!=y)
{
fa[x]=y;
//node[a].prev=node[y].lastson;
node[node[y].lastson].next=x;
node[y].lastson=node[x].lastson;
}
}
int n,m;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
fa[i]=i;
node[i].lastson=i;
}
for(int i=1;i<=m;i++)
{
int t,a,b;
scanf("%d%d%d",&t,&a,&b);
int u=getf(a);
if(t==1)
{
if(getf(a)!=getf(b))
{
if(tag[u])
{
int pt=u;
while(pt)
{
node[pt].val+=tag[u];
pt=node[pt].next;
}
tag[u]=0;
}
int v=getf(b);
if(tag[v])
{
int pt=v;
while(pt)
{
node[pt].val+=tag[v];
pt=node[pt].next;
}
tag[v]=0;
}
merge(a,b);
}
}
else if(t==2)
{
tag[u]+=b;
}
}
for(int i=1;i<=n;i++)
{
if(tag[i])
{
int pt=i;
while(pt)
{
node[pt].val+=tag[i];
pt=node[pt].next;
}
}
tag[i]=0;
}
for(int i=1;i<=n;i++)
{
printf("%lld ",node[i].val);
}
return 0;
}