并查集在区间问题中的简单应用
说实话感觉都已经不像并查集了。
记录下一个操作位置
例如，一个长度为n的区间，有m个操作，形如<li,ri,wi>，表示对[li..ri]这个区间染色成wi的颜色。输出最后的序列。
一眼看过去就是线段树。但是如果要求O(n)复杂度？
Father[x]表示x右边（包括自己）第一个需要操作的格子。初始的时候Father[x]=x。
每一次先跳到Getfather(x)，操作一次，再令Father[x]=Getfather(x+1)。
代码如下：
j:=Getfather(Ope[i].l);
while j<=Ope[i].r do
begin
A[j]:=Ope[i].w;
Father[j]:=Getfather(j+1);
j:=Father[j];
end;
这样覆盖，我们只考虑了这个格子最后一次被覆盖的颜色。所以我们要倒着做。
并且这是一个离线算法，如果不方便离线，或者强制在线，还是玩线段树的好。
这个方法经常会涉及到Fa[n+1]，需要处理一下，令Fa[n+1]=n+1
避免死循环。
C++代码如下：
for(vt=Getfa(li);vt<=ri;vt=Fa[vt]=Getfa(vt+1))A[vt]=wi;
记录区间长度
例如，一个长度为n的区间，有m个条件或者询问。每一个条件形如<li,ri,wi>，表示[li..ri]的区间和为wi（条件不必判错）。每一个询问形如<li,ri>，表示查询[li..ri]的区间和。如果当前信息可以推导出区间和，则输出区间和，否则输出-1。
这个问题用线段树似乎就不太好解决了。但并查集可以完成这一点。
令Dist[x]为x到Father[x]这一段左开右闭的区间。事实上Dist[x]就是x在并查集中的权值（即节点到父亲的边的长度）。
给出了一个<li,ri,wi>，意味着我们可以把Getfather(li-1)并入Getfather(ri)中，同时Father[Getfather(li-1)]=Dist[ri]+w-Dist[li-1]。
fl:=Getfather(l-1);
fr:=Getfather(r);
if fl=fr then continue;
Father[fl]:=fr;
Dist[fl]:=w+Dist[r]-Dist[l-1];
查询[li..ri]的区间和，相当于Dist[li-1]-Dist[ri]。如果li-1与ri不在同一个集合中，那么说明当前信息不能推导出区间和，输出-1。
if Getfather(l-1)=Getfather(r) then writeln(Dist[l-1]-Dist[r])
else writeln('UNKNOWN');