题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4569
这题，出题人是怎么想到的QAQ
真心服 Orz
考虑网络流的区间建边的方法：先搞出一个像线段树的玩意
然而这个题目没办法了，因为线段树的区间拆分是不规则的，对不上 QAQ
于是考虑ST表，用ST表来搞一搞，其实是用来去掉区间合并中的重复部分
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 100000+9;
const int MOD = 1000000007;
int n,m,fa[18][N],vout=1;
inline int find(int p, int w) {
int f = fa[p][w], tmp;
while (f != fa[p][f]) f = fa[p][f];
while (w != f) tmp = fa[p][w], fa[p][w] = f, w = tmp;
return f;
}
inline int read(){
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}
void merge(int t, int a, int b){
int t1 = find(t,a), t2 = find(t, b);
if (t1 == t2) return; fa[t][t1] = t2;
if (!t) return; t--, merge(t,a,b), merge(t,a+(1<<t),b+(1<<t));
}
int main(){
n = read(); m = read(); if (n == 1) return puts("10"), 0;
for (int j=0;j<=17;j++) for (int i=1;i<=n;i++) fa[j][i] = i;
for (int i=1,a,b,c,d,stp;i<=m;i++)
a = read(), b = read(), c = read(), d = read(), stp = 31 - __builtin_clz(b-a+1),
merge(stp,a,c), merge(stp,b-(1<<stp)+1,d-(1<<stp)+1);
for (int i=1,tag=1;i<=n;i++) if (find(0,i) == i) vout = vout*(tag?9LL:10LL) % MOD, tag = 0;
return printf("%d\n",vout), 0;
}
另外说到压代码这个事，Claris我是真心服 (:зゝ∠)
第一眼看上去，还以为只有主要的函数QAQ
再次 Orz
