回顾:st表
f[i][j] 为序列中 i ~ i + 2 j 2^j 2j - 1中的最大(小)值
预处理 f[i][0] = a i a_i ai , f[i][j+1] = max(f[i][j], f[i + (1 << j)][j])
查询 : 对于区间[l, r], 我们将它分解为[l, 2 k 2^k 2k], 和[r - 2 k 2^k 2k + 1, r]两个区间, 它们可能会有重叠, 但取max并不会影响区间最值
回到本题:
如图, 由题意将[l1, r1](黑), [l2, r2](绿)合并
应用st表思想
可以看成将两个红色区间合并, 两个橙色区间合并, 有重复并不影响答案, 因为他只是维护了等量关系
合并可以利用并查集维护
最后枚举从大到小枚举len, 将大区间的等量关系下放到两个小区间上, 最后统计答案即可
代码:
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int N = 100050; int f[N][25]; int read(void) { int x = 0; char c = getchar(); while (!isdigit(c)) c = getchar(); while (isdigit(c)) { x = (x << 3) + (x << 1) + c - '0'; c = getchar(); } return x; } int n, m; int find(int x,int y) { if (f[x][y] == x) return x; return f[x][y] = find(f[x][y], y); } //找爹 inline void merge(int x,int y,int len) { int fx = find(f[x][len], len), fy = find(f[y][len], len); f[f[fx][len]][len] = fy; } //合并 int lo[N]; const int P = 1e9+7; int main() { n = read(), m = read(); lo[0] = -1; for (int i = 1;i <= n; i++) lo[i] = lo[i/2]+1; // 预处理log2(k) for (int i = 1;i <= n; i++) for (int j = 0;j <= 21; j++) f[i][j] = i; while (m--) { int l1 = read(), r1 = read(), l2 = read(), r2 = read(); int len = lo[r1 - l1 + 1]; merge(l1, l2, len); //分成两个小区间 l1 = r1 - (1 << len) + 1, l2 = r2 - (1 << len) + 1; merge(l1, l2, len); } for (int len = 21;len >= 1; len--) { for (int i = 1;i + (1 << len) - 1 <= n; i++) { int fa = find(i, len); if (fa != i) { merge(i, fa, len-1); //大区间分裂成两个小区间 merge(i + (1 << (len-1)), fa + (1 << (len-1)), len - 1); } } } long long ans = 0; for (int i = 1;i <= n; i++) { if (f[i][0] == i) { if (ans == 0) ans = 9; else ans = ans * 10 % P; } } cout << ans % P << endl; return 0; }= 9; else ans = ans * 10 % P; } } cout << ans % P << endl; return 0; }
