题意：

有N个节点，M个操作：连接两个节点、单个节点的权值增加v、节点所在的连通块的所有节点的权值增加v、所有节点的权值增加v、询问节点当前的权值、询问节点所在的连通块中权值最大的节点的权值、询问所有节点中权值最大的节点的权值。N，M≤300000

题解：

可并堆，虽然听说配对堆非常快，但教程太少了不会写，所以去学了斜堆，比较好写。斜堆实际上是一棵二叉树，核心是合并操作，这是一个递归过程，有点像treap的删除操作。斜堆保证复杂度的方法是每次递归合并右节点，合并完后交换左右节点，使整棵树和splay一样，可以“自动”平衡，也是玄学。要修改整个连通块，打标记就行了。这道题特殊的一点在于询问所有节点权值的最大值，可以用STL的set维护所有连通块的根节点，当连边和修改权值时如果根节点被修改需要维护一下set。

代码：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #define inc(i,j,k) for(int i=j;i<=k;i++) 6 #define maxn 300100 7 #define INF 0x3fffffff 8 using namespace std; 9 10 int fa[maxn],ch[maxn][2],tg[maxn],v[maxn],n,m,add;11 multiset 
         
           st;12 void pushdown(int x){13     if(tg[x]){14         if(ch[x][0])tg[ch[x][0]]+=tg[x],v[ch[x][0]]+=tg[x];15         if(ch[x][1])tg[ch[x][1]]+=tg[x],v[ch[x][1]]+=tg[x];16         tg[x]=0;17     }18 }19 int dt[maxn],dts;20 int find(int x){21     dt[dts=1]=x; while(fa[x])x=fa[x],dt[++dts]=x;22     for(int i=dts;i>=1;i--)pushdown(dt[i]); return x;23 }24 int merge(int x,int y){25     if(!x||!y)return x+y; if(v[x]
         
        
       
      
     

 

20160530