并查集

起初我也不懂，后来是看了题解才懂的

感谢

 

尽力讲清楚吧..

带权并查集..

并查集在路径压缩时顺带把并查集上的边权也压缩

设 sum[i] 表示船 i 前面有多少船，不包括 i

求两船之间有多少船，只要把后面的sum减去前面的sum

#include
     
      #include
      
       #include
       
        using namespace std;inline int read(){    int 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<<1)+(x<<3)+(ch^48);        ch=getchar();    }    return x*f;}int n;int fa[30007],sum[30007],sz[30007]; //sz[i]表示船i所在的行队列的大小inline int find(int x){    if(fa[x]==x) return x;    int k=fa[x];    fa[x]=find(fa[x]);//先更新前面的船的sum和sz    sum[x]+=sum[k]; 　　 //利用前面的信息更新当前信息，注意是"+=sum[k]",因为之前可能也压缩过（即x和k之间可能隔着船）    sz[x]=sz[fa[x]];//更新sz    return fa[x];}//并查集带权路径压缩（核心代码）int main(){    for(int i=1;i<=30005;i++) fa[i]=i,sz[i]=1;//初始化    int a,b;    char ch;    cin>>n;    while(n--)    {        cin>>ch;        a=read(); b=read();        if(ch=='M')        {            int xa=find(a),xb=find(b);            //cout<
        
         <<" "<
         
          <