背景
(CCF) (NOI) (2002) (T1) ， (Luogu) (P1196/Vijos1443)
题意
给出 (30000) 艘战舰排成一行（从 (1) 到 (30000) 编号），每艘独占一列。给出 (T) 条指令，形如 (M x y) 或 (C x y) ，前一个表示第 (x) 号战舰所在的一列战舰整体平移到第 (y) 号战舰所在的一列战舰的后方，后一个表示查询第 (x) 号战舰和第 (y) 号战舰是否在同一列，若是的话还要查询两艘战舰之间隔着几艘战舰。
解法
考虑把每个战舰当做一个集合，用并查集维护当前战舰所在的集合的首个元素。当然，仅仅这样是不够的。由于要查询两艘战舰之间隔着几艘战舰，考虑维护每艘战舰 (x) 到首个元素（列首）的距离 (d_x) 。对于一个 (M) 操作，相当于是把 (x) 的代表元素作为 (y) 所在集合的一个节点，于是向 (y) 的代表元素合并 (x) 的代表元素即可。
考虑合并的过程怎么更新 (d_x) 。求 (d_x) 的过程就是把它到根节点之间的所有边权求个和。于是魔改一下查询代表元素的函数即可。合并完之后考虑 (d_x) 已经被更新了，新的值是 (y) 所在集合的总战舰数，于是还要记一个 (siz_x) 表示节点 (x) 所在集合的元素数。也要动态维护。
然后是 (C) 操作。显然直接查询 (x) 的代表元素和 (y) 的代表元素是否相同即可判定是否在同一列。然后两艘战舰之间隔着的战舰数就是 (left| d_x-d_y
ight| -1) ，即两点到代表元素的距离之差减去一个元素的值。
(trick)
为每个节点 (i) 安排一个权值 (d_i) 用来回答询问或者判定合法性。注意 (d) 数组的维护方法（先递归找代表再累加权值）。
代码
$View$ $Code$
//省略头文件 using namespace std; inline int read() { int ret=0,f=1; char ch=getchar(); while(ch>'9'||ch<'0') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { ret=(ret<<1)+(ret<<3)+ch-'0'; ch=getchar(); } return ret*f; } int T,x,y,fa[30005],d[30005],siz[30005]; char op; int get(int x) { if(x==fa[x]) return x; int rt=get(fa[x]); d[x]+=d[fa[x]]; return fa[x]=rt; } int main() { T=read(); for(register int i=1;i<=30000;i++) { fa[i]=i; siz[i]=1; } while(T--) { scanf("%c",&op); x=read(); y=read(); if(op=='C') { int fx=get(x),fy=get(y); if(fx!=fy) printf("-1 "); else printf("%d ",abs(d[x]-d[y])-1); } else { int fx=get(x),fy=get(y); fa[fx]=fy; d[fx]=siz[fy]; siz[fy]+=siz[fx]; } } return 0; }