Description
一个长度为n的大数，用S1S2S3...Sn表示，其中Si表示数的第i位,S1是数的最高位，告诉你一些限制条件，每个条
件表示为四个数，l1，r1，l2，r2，即两个长度相同的区间，表示子串Sl1Sl1+1Sl1+2...Sr1与Sl2Sl2+1Sl2+2...S
r2完全相同。比如n=6时，某限制条件l1=1，r1=3，l2=4，r2=6，那么123123，351351均满足条件，但是12012，13
1141不满足条件，前者数的长度不为6，后者第二位与第五位不同。问满足以上所有条件的数有多少个。
Input
第一行两个数n和m，分别表示大数的长度，以及限制条件的个数。接下来m行，对于第i行,有4个数li1，ri1，li2
，ri2，分别表示该限制条件对应的两个区间。
1≤n≤10^5，1≤m≤10^5，1≤li1,ri1,li2,ri2≤n；并且保证ri1-li1=ri2-li2。
Output
一个数，表示满足所有条件且长度为n的大数的个数，答案可能很大，因此输出答案模10^9+7的结果即可。
Sample Input
4 2
1 2 3 4
3 3 3 3
1 2 3 4
3 3 3 3
Sample Output
90
HINT
Source
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ST表+并查集+思路～
用ST表的思想来记录区间之间的固定关系，f[i][j]表示[i,i+(1<<j)-1]之内是一段，那么它是由f[i][j-1]和f[i+(1<<(j-1))][j-1]更新得来的，所以我们要合并一个区间，首先要合并它的左右子区间。我们用并查集来记录这种合并关系。
最后答案就是9*10^(区间数-1)。
因为数组开小了导致数组顺序改变后就RE了。写这道题的时候要注意！
#include<cstdio>
#include<iostream>
using namespace std;
#define ll long long
#define mod 1000000007int n,m,l1,l2,r1,r2,mi[19],fa[1900019],id[100001][19],f[1900019][2],tot,ans,cnt;int read()
{int x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;
}int find(int u)
{return fa[u] ? fa[u]=find(fa[u]):u;
}void merge(int u,int v)
{int x=find(u),y=find(v);if(x!=y) fa[x]=y;
}int main()
{n=read();m=read();mi[0]=1;if(n==1){printf("10\n");return 0;}for(int i=1;i<=18;i++) mi[i]=mi[i-1]<<1;for(int i=1;i<=n;i++)for(int j=0;j<=18;j++) id[i][j]=++cnt,f[cnt][0]=i,f[cnt][1]=j;for(int i=1;i<=m;i++){l1=read();r1=read();l2=read();r2=read();for(int j=18;~j;j--)if(l1+mi[j]-1<=r1){merge(id[l1][j],id[l2][j]);l1+=mi[j];l2+=mi[j];}}for(int j=18;j;j--)for(int i=1;i<=n;i++){int k=find(id[i][j]),s=f[k][0],t=f[k][1];merge(id[s][t-1],id[i][j-1]);merge(id[s+mi[t-1]][t-1],id[i+mi[j-1]][j-1]);}for(int i=1;i<=n;i++) if(!fa[id[i][0]]) tot++;ans=9;for(int i=1;i<tot;i++) ans=(ll)ans*10%mod;printf("%d\n",ans);return 0;
}