ZOJ 2334左偏树+并查集 - c++编程基础

题意很好理解……

这左偏树看了上交模板，但是不知道怎么用，研究了左偏树好久……才会一点点……

左偏树的操作都是建立在合并上，所以合并后的堆顶编号极其重要，我就是这里搞了半天，才知道这里错了。

然后又查了其他资料，才弄清楚，因为在合并中有：dist[x]=dist[r[x]]+1;，所以合并的编号应该是更新 root[right] 的。

参考博客：https://www.byvoid.com/blog/leftist-tree/

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
              #include 
              
                #include 
               
                 #define PI acos(-1.0) #define mem(a,b) memset(a,b,sizeof(a)) #define sca(a) scanf("%d",&a) #define sc(a,b) scanf("%d%d",&a,&b) #define pri(a) printf("%d\n",a) #define lson i<<1,l,mid #define rson i<<1|1,mid+1,r #define MM 1000004 #define MN 1008 #define INF 100000007 #define eps 1e-7 using namespace std; typedef long long LL; typedef unsigned long long ULL; int f[MM],root[MM]; //root是初始每个左偏树的堆顶编号 int tot,v[MM],l[MM],r[MM],dist[MM]; int Merge(int x,int y) { if(!x) return y; if(!y) return x; if(v[x]