BZOJ4569 : [Scoi2016]萌萌哒

建立ST表，每层维护一个并查集。

每个信息可以拆成两条长度为$2$的幂次的区间相等的信息，等价于ST表里两对点的合并。

然后递归合并，一旦发现已经合并过了就退出。

因为一共只会发生$O(n\log n)$次合并，所以时间复杂度为$O(n\log n\alpha(n))$。

#include
int n,m,i,j,a,b,c,d,f[17][100010],v[100010],ans=9;
int F(int i,int j){return f[i][j]==j?j:f[i][j]=F(i,f[i][j]);}
void merge(int p,int x,int y){
  if(F(p,x)==F(p,y))return;
  f[p][f[p][x]]=f[p][y];
  if(!p)return;
  p--;
  merge(p,x,y),merge(p,x+(1<=‘0‘)&&(c<=‘9‘)));a=c-‘0‘;while(((c=getchar())>=‘0‘)&&(c<=‘9‘))(a*=10)+=c-‘0‘;}
int main(){
  read(n),read(m);
  if(n==1)return puts("10"),0;
  for(i=0;(1<