做法：st表+并查集

前置芝士：

st表：https://oi-wiki.org/ds/sparse-table/

思路：

  • 令f[i][j]表示区间[i,i+ 2^j-1]这一段
  • 对于一个限制可以拆成log 份，然后进行集合合并
  • 答案就是是9*10^(集合个数-1)

代码

// Problem: [SCOI2016]萌萌哒
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/problem/20310
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp(aa,bb) make_pair(aa,bb)
#define _for(i,b) for(int i=(0);i<(b);i++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,b,a) for(int i=(b);i>=(a);i--)
#define mst(abc,bca) memset(abc,bca,sizeof abc)
#define X first
#define Y second
#define lowbit(a) (a&(-a))
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long double ld;
const int N=1e5+10;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-6;
const double PI=acos(-1.0);

int n,m;
int lg[N],fa[N][20];

void init(){
    for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=lg[n];j++){
            fa[i][j]=i;
        }
    }
}

ll fpow(ll a,ll b,ll mod){
    if(mod==1) return 0;
    ll ans=1%mod;
    while(b){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

int find(int x,int y){
    if(x!=fa[x][y]) fa[x][y]=find(fa[x][y],y);
    return fa[x][y];
}

void unite(int a,int b,int len){
    a=find(fa[a][len],len),b=find(fa[b][len],len);
    fa[fa[a][len]][len]=fa[fa[b][len]][len];
}

void solve(){
    cin>>n>>m;
    init();
    while(m--){
        int l1,r1,l2,r2;cin>>l1>>r1>>l2>>r2;
        int s=lg[r1-l1+1];
        unite(l1,l2,s);
        unite(r1-(1<<s)+1,r2-(1<<s)+1,s);
    }

    for (int s=lg[n];s>=1;s--){
        for (int i=1;i+(1<<s)-1<=n;i++) {
            int fa=find(i,s);
            if (fa!=i){
                unite(i,fa,s-1); //大区间分裂成两个小区间
                unite(i+(1<<(s-1)),fa+(1<<(s-1)),s-1);
            }
        }
    }

    int cnt=0;
    for(int i=1;i<=n;i++){
        if(fa[i][0]==i){
            cnt++;
        }
    }
    cout<<9*fpow(10,cnt-1,mod)%mod<<"\n";
}


int main(){
    ios::sync_with_stdio(0);cin.tie(0);
//    int t;cin>>t;while(t--)
    solve();
    return 0;
}