如果给相同的位置连边，最后联通块数是n，最后答案就是$9*10^{n-1}$

但直接连边是$O(n^2)$的

所以事先处理出一个ST表，每次O(1)地给那个ST表连边

最后再一点一点下放，就是把在这层的同一集合的的左儿子连到一个里，右儿子连到一个里

统计最下面那一层的联通块数量就行了

1 #include
     
       2 #define pa pair
      
        3 #define CLR(a,x) memset(a,x,sizeof(a)) 4 using namespace std; 5 typedef long long ll; 6 const int maxn=1e5+10,logn=20,P=1e9+7; 7  8 inline ll rd(){ 9     ll x=0;char c=getchar();int neg=1;10     while(c<'0'||c>'9'){
   if(c=='-') neg=-1;c=getchar();}11     while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();12     return x*neg;13 }14 15 int id[maxn][20],pct,fa[maxn*logn],ch[maxn*logn][2];16 int N,M;17 bool flag[maxn*logn];18 19 inline int getf(int x){
   return fa[x]==x?x:fa[x]=getf(fa[x]);}20 inline void makest(){21     for(int i=N;i;i--){22         id[i][0]=++pct;23         for(int j=0;id[i][j]&&id[i+(1<