OI笔记 | 2023.7-11 做题记录（二）
- k 小值
- [USACO09NOV] Lights G
- [USACO18OPEN] Talent Show G
- 线段树优化建图
- [APIO2008] 免费道路
- [ARC126C] Maximize GCD
- 二分图完美匹配方案数
- Count Bracket Sequences
- Company
- [SCOI2016] 萌萌哒
k 小值
有两个长度为 $n$ 的数组 $a,b$，数组内的元素单调不降。
$q$ 次操作，操作有两种：
-
单点修改：$a_x\gets y$ 或 $b_x\gets y$。保证修改后的数组内的元素仍单调不降。
-
查询：将 $a$ 数组的 $[l_1,r_1]$ 内的元素和 $b$ 数组的 $[l_2, r_2]$ 内的元素合并在一起，查询这些元素的第 $k$ 小值。
$1\leq n\leq 5\times 10^5, 1\leq q,a_i,b_i\leq 10^6$
题解
Solution 1
$\mathcal{O}(q\log n\log a_i)$，考虑二分答案 $mid$，在两个数组中二分查找比它小的数有多少个。此方法无法通过本题。
int L = 0, R = MAX_V;
while(L < R - 1) {
int mid = L + ((R - L) >> 1);
int pos1 = lower_bound(a + l1, a + r1 + 1, mid) - a - l1;
int pos2 = lower_bound(b + l2, b + r2 + 1, mid) - b - l2;
if(pos1 + pos2 >= k) R = mid;
else L = mid;
}
Solution 2
$\mathcal{O}(q\log n)$，考虑分治（或者说倍增的一种递归实现）。设答案为 $f(l_1,r_1,l_2,r_2,k)$，则我们令 $s=l_1+\lfloor \frac{k}{2}\rfloor -1, t = l_2+\lfloor \frac{k}{2}\rfloor -1$，若 $a_s<b_t$，则 $a_{l_1},a_{l_2},\dots a_{s}$ 都不可能成为答案，所以 $f(l_1,r_1,l_2,r_2,k)=f(s+1,r_1,l_2,r_2,k-(s-l_1+1))$。若 $a_s\geq b_t$ 同理。
每次都可以舍掉其中一个区间的一半，因此时间复杂度可以保证通过本题。递归实现即可，注意边界处理。
int f(int l1, int r1, int l2, int r2, int k) {
if(l1 > r1) return b[l2 + k - 1];
if(l2 > r2) return a[l1 + k - 1];
if(k == 1) return min(a[l1], b[l2]);
int s = min(l1 + (k >> 1) - 1, r1), t = min(l2 + (k >> 1) - 1, r2);
if(a[s] < b[t]) return f(s + 1, r1, l2, r2, k - (s - l1 + 1));
else return f(l1, r1, t + 1, r2, k - (t - l2 + 1));
}
[USACO09NOV] Lights G
给出一张 $n$ 个点 $m$ 条边的无向图，每个点的初始状态都为 $0$。
你可以操作任意一个点，操作结束后该点以及所有与该点相邻的点的状态都会改变，由 $0$ 变成 $1$ 或由 $1$ 变成 $0$。
你需要求出最少的操作次数，使得在所有操作完成之后所有 $n$ 个点的状态都是 $1$。
$1\le n\le35,1\le m\le595, 1\le a,b\le n$。
题解
经典开关问题的无向图上版本。
显然可以枚举搜索每个点选不选，也可以高斯消元。
这里我们使用搜索，但是 $2^{35}$ 无法接受，所以可以使用 Meet in the middle 思想，把节点拆成 $1\sim \lfloor \frac{n}{2}\rfloor $ 和 $(\lfloor \frac{n}{2}\rfloor + 1)\sim n$ 两部分，分别进行搜索，并且考虑搜索的同时把两边的状态合并。
时间复杂度 $\mathcal{O}(n2^{\frac{n}{2}})$。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 40;
int n, m, ans;
ll aim, v[MAX_N];
map<ll, int> step;
void dfs(int u, int r, ll state, int cnt) {
if(step.count(state)) step[state] = min(step[state], cnt);
else step[state] = cnt;
if(state == aim) ans = min(ans, cnt);
if(u > (n >> 1) && step.count(state ^ aim)) ans = min(ans, step[state ^ aim] + cnt);
if(u > r) return;
dfs(u + 1, r, state, cnt);
dfs(u + 1, r, (state ^ v[u]), cnt + 1);
}
int main() {
n = read(), m = read();
for(int i = 1; i <= n; i++)
v[i] |= (1ll << i);
for(int i = 1; i <= m; i++) {
int a = read(), b = read();
v[a] |= (1ll << b);
v[b] |= (1ll << a);
}
aim = (((1ll << n) - 1) << 1), ans = n;
dfs(1, (n >> 1), 0, 0);
dfs((n >> 1) + 1, n, 0, 0);
write(ans), putchar('\n');
return 0;
}
[USACO18OPEN] Talent Show G
$n$ 头奶牛，第 $i$ 头奶牛重量为 $w_i$，才艺水平为 $t_i$。
从中选一些参加比赛的奶牛。这些奶牛的总重量至少为 $W$。
最大化选出奶牛的才艺和与重量和的比值。
$1 \leq n \leq 250$，$1 \leq W \leq 1000$，$1 \leq w_i \leq 10^6$，$1 \leq t_i \leq 10^3$。
题解
01分数规划板子。
题意相当于最大化 $\frac{\sum p_i t_i}{\sum p_i w_i}$，其中 $p_i\in \left{ 0,1\right}$。二分答案 $x$，则答案合法，当且仅当 $\frac{\sum p_i t_i}{\sum p_i w_i}> x\iff \sum p_i(t_i-xw_i)>0$。所以转化成选出一些奶牛，重量为 $w_i$，价值为 $t_i-xw_i$，且满足重量和至少为 $W$。跑一个 01 背包即可，则式子左边的最大值为 $dp_{W}$。
时间复杂度 $\mathcal{O}(nW\log W)$。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {...}
char buf[50];
inline void write(ll x) {...}
const int MAX_N = 255, MAX_W = 1005;
const double MAX_ANS = 1e3 + 1, eps = 1e-4, INF = 1e9;
int n, W, w[MAX_N], t[MAX_N];
double dp[MAX_W];
bool check(double x) {
for(int i = 1; i <= W; i++)
dp[i] = -INF;
for(int i = 1; i <= n; i++)
for(int j = W; j >= 0; j--) {
int k = min(W, j + w[i]);
dp[k] = max(dp[k], dp[j] + t[i] - x * w[i]);
}
return dp[W] > 0;
}
int main() {
n = read(), W = read();
for(int i = 1; i <= n; i++)
w[i] = read(), t[i] = read();
double l = 0, r = MAX_ANS;
while(r - l > eps) {
double mid = (l + r) * 0.5;
if(check(mid)) l = mid;
else r = mid;
}
write(int(1000 * l));
return 0;
}
线段树优化建图
有一个 $n$ 个点的有向图，初始没有点有连边。
$q$ 次操作，操作有三种：
1 v u w：连边 $(v,u,w)$。
2 v l r w：$\forall \ l\leq u\leq r$，连边 $(v,u,w)$。
3 v l r w：$\forall\ l\leq u\leq r$，连边 $(u,v,w)$。
在所有操作后，求 $s$ 到所有点的最短距离。
$1\leq n,q\leq 10^5, 1\leq w\leq 10^9$
题解
如果暴力建边，时空复杂度无法接受。由于有区间操作，我们可以考虑使用线段树来优化。
我们可以把线段树上的节点纳入原图中考虑，原图中的点 $1\sim n$ 对应线段树的叶子节点，线段树的其他节点对应一些区间。
建立两棵线段树，一个入树，一个出树。对于入树，从左右儿子向父亲连零边；对于出树，从父亲向左右儿子连零边。并且，我们把入树和出树的相同的叶子节点相互连零边。这样以来，最后的最短路就是从 $s$ 对应入树的叶子节点出发，到达出树的叶子节点的距离。
那么操作 $2$ 相当于 $v$ 对应入树的叶子节点向区间 $[l,r]$ 对应出树的节点连边；操作 $3$ 同理。
#include <bits/stdc++.h>
#define pb emplace_back
using namespace std;
typedef long long ll;
typedef pair<ll, int> pii;
inline ll read() {...}
char buf[50];
inline void write(ll x) {...}
const int MAX_N = 3e6 + 10, DELTA = 5e5;
const ll INF = (1ll << 60);
int n, q, s, cnt, leaf1[MAX_N], leaf2[MAX_N], fir[MAX_N];
bool vis[MAX_N];
ll dis[MAX_N];
struct edge {
int v, w, nxt;
edge() { }
edge(int _v, int _w, int _nxt) :
v(_v), w(_w), nxt(_nxt) { }
} e[MAX_N << 2];
void AddEdge(int u, int v, int w) {
e[++cnt] = edge(v, w, fir[u]);
fir[u] = cnt;
}
inline int lc(int p) { return (p << 1); }
inline int rc(int p) { return (p << 1) | 1;}
inline int mid(int s, int t) { return s + ((t - s) >> 1); }
void build_tree(int s, int t, int p) {
if(s == t) {
leaf1[s] = p;
leaf2[s] = p + DELTA;
AddEdge(leaf1[s], leaf2[s], 0);
AddEdge(leaf2[s], leaf1[s], 0);
return;
}
int m = mid(s, t);
AddEdge(p, lc(p), 0), AddEdge(p, rc(p), 0);
AddEdge(lc(p) + DELTA, p + DELTA, 0), AddEdge(rc(p) + DELTA, p + DELTA, 0);
build_tree(s, m, lc(p));
build_tree(m + 1, t, rc(p));
}
void update(int s, int t, int p, int l, int r, int u, int type, int w) {
if(l <= s && t <= r) {
if(type == 2) AddEdge(leaf2[u], p, w);
else AddEdge(p + DELTA, leaf1[u], w);
return;
}
int m = mid(s, t);
if(l <= m) update(s, m, lc(p), l, r, u, type, w);
if(r > m) update(m + 1, t, rc(p), l, r, u, type, w);
}
void dijkstra(int s) {
priority_queue<pii, vector<pii>, greater<pii>> pq;
for(int i = 1; i < MAX_N; i++)
dis[i] = INF;
pq.push(make_pair(0, s));
dis[s] = 0;
while(!pq.empty()) {
int u = pq.top().second; pq.pop();
if(vis[u]) continue;
vis[u] = 1;
for(int i = fir[u]; i; i = e[i].nxt) {
int v = e[i].v, w = e[i].w;
if(dis[u] + w < dis[v]) {
dis[v] = dis[u] + w;
pq.push(make_pair(dis[v], v));
}
}
}
}
int main() {
n = read(), q = read(), s = read();
build_tree(1, n, 1);
while(q--) {
int type = read();
if(type == 1) {
int v = read(), u = read(), w = read();
AddEdge(leaf2[v], leaf1[u], w);
}
else {
int v = read(), l = read(), r = read(), w = read();
update(1, n, 1, l, r, v, type, w);
}
}
dijkstra(leaf2[s]);
for(int i = 1; i <= n; i++)
write(dis[leaf1[i]] == INF ? -1 : dis[leaf1[i]]), putchar(" \n"[i == n]);
return 0;
}
Bonus
洛谷 P6348：要求支持区间 $[a,b]$ 向区间 $[c,d]$ 连边。
这个可以通过建两个虚点 $x,y$，然后在入树将 $[a,b]$ 连到 $x$，在出树将 $y$ 连到 $[c,d]$，然后再连边 $(x,y,w)$ 即可。
[APIO2008] 免费道路
有一个 $N$ 个点，$M$ 条边的无向图，边有黑白两种。要求找出原图的一个生成树，使得树上正好有 $K$ 条白边。
$1\leq N\leq 2\times 10^4,1\leq M\leq 10^5, 0\leq K \leq N - 1$
题解
先按黑边优先来排序，跑一遍 Kruskal，求出加入的白边数量的最小值 $p$，以及此时加入了哪些白边。若 $p>K$，则无解。
再跑一遍 Kruskal，这次优先加入那些必须要加的白边，然后再加其他白边直到达到 $K$ 条，其次再加其他黑边。若白边达不到 $K$ 条或加完之后无法形成生成树，则无解。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
inline ll read() {...}
char buf[50];
inline void write(ll x) {...}
const int MAX_N = 1e5 + 10;
int n, m, k, cnt, tot;
struct edge { int u, v, w; } E[MAX_N], ans[MAX_N];
struct dsu {
int fa[MAX_N];
dsu(int n) {
for(int i = 1; i <= n; i++)
fa[i] = i;
}
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
bool merge(int x, int y) {
int fx = find(x), fy = find(y);
if(fx == fy) return 0;
fa[fx] = fy;
return 1;
}
};
void solve() {
sort(E + 1, E + m + 1, [](edge x, edge y) { return x.w > y.w; });
dsu D = dsu(n);
for(int i = 1; i <= m; i++) {
bool f = D.merge(E[i].u, E[i].v); tot += f;
if(f && E[i].w == 0) cnt++, E[i].w = -1;
}
if(cnt > k || tot != n - 1) { puts("no solution"); return; }
sort(E + 1, E + m + 1, [](edge x, edge y) { return x.w < y.w; });
D = dsu(n);
cnt = tot = 0;
for(int i = 1; i <= m; i++) {
if(cnt == k && E[i].w <= 0) continue;
bool f = D.merge(E[i].u, E[i].v);
if(f) ans[++tot] = E[i];
if(f && E[i].w <= 0) cnt++;
}
if(cnt < k || tot != n - 1) { puts("no solution"); return; }
for(int i = 1; i <= tot; i++) {
write(ans[i].u), putchar(' ');
write(ans[i].v), putchar(' ');
write(max(ans[i].w, 0)), putchar('\n');
}
}
int main() {
n = read(), m = read(), k = read();
for(int i = 1; i <= m; i++)
E[i].u = read(), E[i].v = read(), E[i].w = read();
solve();
return 0;
}
[ARC126C] Maximize GCD
给定一个序列 $A$，每次操作可以使 $A_i + 1$ （$i \in [1, n]$，$K$ 次操作的 $i$ 可以不同），最多可以做 $K$ 次。问 $\gcd{A_1, A_2, …, A_n}$ 的最大值。
$ 2\leq\ N\leq\ 3\times\ 10^5 , 1\leq\ K\leq\ 10^{18} ,1\ \leq\ A_i\leq\ 3\times\ 10^5 $
题解
设序列 $A$ 中的最大值为 $t$。
当 $K\geq \sum\limits_{i=1}^n (t - A_i)$ 时，显然我们可以把所有数先加到 $t$，然后把剩下的操作次数平均分给每一个数，得到最大的答案。
否则，答案一定小于 $t$，我们就从 $t$ 到 $1$ 枚举 $ans$，检验它的合法性。要让所有数的 $\gcd$ 等于 $ans$，我们就让每个数加到它以上的最接近的 $ans$ 的倍数，所以需要的最少次数为 $\sum\limits_{i=1}^n (\lceil \frac{A_i}{ans} \rceil\times ans - A_i)$，判断它与 $K$ 的大小关系即可。
考虑加速上面式子的计算。我们发现 $\lceil \frac{A_i}{ans} \rceil$ 的取值是连续的，对于 $A_i\in ((k-1)\cdot ans, k\cdot ans]$，取值均为 $k$。所以把 $A_i$ 按值域分成 $\lceil \frac{t}{ans} \rceil$ 段，每一段的答案为 $k\cdot ans\cdot cnt-sum$，其中 $cnt$ 为区间中 $A_i$ 的数量，$sum$ 为区间中 $A_i$ 的和，这些都可以预处理。
所以最终的时间复杂度为 $\mathcal{O}(n \ln n)$。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {...}
inline void write(ll x) {...}
const int MAX_N = 6e5 + 10;
ll n, K, delta, a[MAX_N], cnt[MAX_N], sum[MAX_N];
bool check(int ans) {
ll p = 0;
for(ll k = 1; k <= (a[n] + ans) / ans; k++) {
ll l = ans * (k - 1), r = ans * k;
p += k * ans * (cnt[r] - cnt[l]) - (sum[r] - sum[l]);
}
return p <= K;
}
int main() {
n = read(), K = read();
for(int i = 1; i <= n; i++)
a[i] = read();
sort(a + 1, a + n + 1);
for(int i = 1; i <= n; i++)
delta += a[n] - a[i];
if(delta <= K) write(a[n] + (K - delta) / n);
else {
for(int i = 1; i <= n; i++)
cnt[a[i]]++;
for(int i = 1; i <= 2 * a[n]; i++)
sum[i] = sum[i - 1] + cnt[i] * i, cnt[i] += cnt[i - 1];
int ans = a[n] - 1;
for(; ans >= 1; ans--)
if(check(ans)) break;
write(ans), putchar('\n');
}
return 0;
}
二分图完美匹配方案数
有一个左部和右部均为 $n$ 个点的二分图，求它的完美匹配方案数。
这个可以状压 dp，设 $dp[i][S]$ 为考虑到左部的第 $i$ 个点，右部的选择情况为状态 $S$ 的方案数。显然 $i=\text{popcount}(S)$，所以可以省略掉第一维。有转移方程如下：
\[dp[S]=\sum dp[S\oplus 2^j]\]其中 $j$ 为在 $S$ 中选中的右部点，且需要满足 $i$ 和 $j$ 有连边。
n = read();
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
a[i][j] = read();
S = (1 << n) - 1;
dp[0] = 1;
for(int s = 1; s <= S; s++) {
int i = __builtin_popcount(s) - 1;
for(int j = 0; j < n; j++)
if(a[i][j] && ((s >> j) & 1)) (dp[s] += dp[s ^ (1 << j)]) %= MOD;
}
write(dp[S]);
Count Bracket Sequences
给定一个非空字符串包含 (，) 和 ?。
其中 ? 需要用 ( 或者 ) 替换掉，求替换后的字符串是合法的括号串的方案数对 $ 998244353$ 取模的值。
题解
对于合法括号序列的判定问题，我们往往将左括号视为 $1$，右括号视为 $-1$，则序列为合法括号序列的充要条件为：
-
序列所有数之和为 $0$。
-
序列的所有前缀和都非负。
所以考虑 $f_{i,j}$ 表示考虑前 $i$ 个数，前缀和为 $j$ 的方案数。
如果第 $i$ 位是左括号，则 $f_{i,j}=\sum f_{i-1,j-1}$。
如果第 $i$ 位是右括号，则 $f_{i,j}=\sum f_{i-1,j+1}$。
如果第 $i$ 位是问号，则 $f_{i,j}=\sum f_{i-1,j-1} + \sum f_{i-1,j+1}$
时间复杂度：$\mathcal{O}(n^2)$。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read() {...}
inline void write(ll x) {...}
const int MAX_N = 3005, MOD = 998244353;
char s[MAX_N];
int n, dp[MAX_N][MAX_N];
int main() {
scanf("%s", s + 1);
n = strlen(s + 1);
dp[0][0] = 1;
for(int i = 1; i <= n; i++) {
if(s[i] == '(') {
for(int j = 1; j <= i; j++)
(dp[i][j] += dp[i - 1][j - 1]) %= MOD;
}
else if(s[i] == ')') {
for(int j = 0; j < i; j++)
(dp[i][j] += dp[i - 1][j + 1]) %= MOD;
}
else {
for(int j = 1; j <= i; j++)
(dp[i][j] += dp[i - 1][j - 1]) %= MOD;
for(int j = 0; j < i; j++)
(dp[i][j] += dp[i - 1][j + 1]) %= MOD;
}
}
write(dp[n][0]);
return 0;
}
Company
给定一颗树，有若干个询问，每个询问给出 $l$，$r$，要求编号为 $l$~$r$ 的点任意删去一个之后剩余点的 LCA 深度最大，输出删去点的编号和 LCA 的最大深度。
题解
经典小 Trick：一个点集内的点的 LCA 为他们之中 dfn 最大和 dfn 最小的点的 LCA。
所以，只有当删的点是 dfn 最大或最小的点时，LCA 才有可能改变。分两类讨论，用 ST 表维护 dfn 序的最大最小值的位置即可。
#include <bits/stdc++.h>
#define pb emplace_back
using namespace std;
typedef long long ll;
inline ll read() {...}
inline void write(ll x) {...}
const int MAX_N = 100005, MAX_LOG = 18;
int n, q, dfncnt, dep[MAX_N], dfn[MAX_N], fa[MAX_N][MAX_LOG];
int log_2[MAX_N], stmin[MAX_N][MAX_LOG], stmax[MAX_N][MAX_LOG];
vector<int> G[MAX_N];
int Min(int x, int y) { return dfn[x] < dfn[y] ? x : y; }
int Max(int x, int y) { return dfn[x] > dfn[y] ? x : y; }
int qmin(int l, int r) {
int len = log_2[r - l + 1];
return Min(stmin[l][len], stmin[r - (1 << len) + 1][len]);
}
int qmax(int l, int r) {
int len = log_2[r - l + 1];
return Max(stmax[l][len], stmax[r - (1 << len) + 1][len]);
}
void pre(int N) {
log_2[1] = 0, log_2[2] = 1;
for(int i = 3; i <= N; i++)
log_2[i] = log_2[i >> 1] + 1;
}
void dfs(int u) {
dfn[u] = ++dfncnt;
dep[u] = dep[fa[u][0]] + 1;
for(int i = 1; i < MAX_LOG; i++)
fa[u][i] = fa[fa[u][i - 1]][i - 1];
for(int v : G[u])
dfs(v);
}
int lca(int x, int y) {
if(!x || !y) return x + y;
if(dep[x] < dep[y]) swap(x, y);
for(int i = MAX_LOG - 1; i >= 0; i--)
if(fa[x][i] && dep[fa[x][i]] >= dep[y]) x = fa[x][i];
if(x == y) return x;
for(int i = MAX_LOG - 1; i >= 0; i--)
if(fa[x][i] && fa[y][i] && fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
return fa[x][0];
}
int cal(int l, int mid, int r) {
int lca1, lca2;
if(l < mid) lca1 = lca(qmin(l, mid - 1), qmax(l, mid - 1));
if(mid < r) lca2 = lca(qmin(mid + 1, r), qmax(mid + 1, r));
if(mid == r) return lca1;
if(mid == l) return lca2;
return lca(lca1, lca2);
}
int main() {
n = read(), q = read();
pre(n);
for(int i = 2; i <= n; i++) {
fa[i][0] = read();
G[fa[i][0]].pb(i);
}
dfs(1);
for(int i = 1; i <= n; i++)
stmin[i][0] = stmax[i][0] = i;
for(int j = 1; j < MAX_LOG; j++)
for(int i = 1; i + (1 << j) - 1 <= n; i++) {
stmin[i][j] = Min(stmin[i][j - 1], stmin[i + (1 << (j - 1))][j - 1]);
stmax[i][j] = Max(stmax[i][j - 1], stmax[i + (1 << (j - 1))][j - 1]);
}
while(q--) {
int l = read(), r = read();
int mn = qmin(l, r), mx = qmax(l, r);
int ans1 = cal(l, mn, r), ans2 = cal(l, mx, r);
if(dep[ans1] > dep[ans2]) write(mn), putchar(' '), write(dep[ans1] - 1);
else write(mx), putchar(' '), write(dep[ans2] - 1);
putchar('\n');
}
}
[SCOI2016] 萌萌哒
一个长度为 $n$ 的大数，用 $S_1S_2S_3 \cdots S_n$表示，其中 $S_i$ 表示数的第 $i$ 位, $S_1$ 是数的最高位。有 $m$ 个限制条件，每个条件表示为四个数，$l_1,r_1,l_2,r_2$，即两个长度相同的区间，表示子串$S_{l_1}S_{l_1+1}S_{l_1+2} \cdots S_{r_1}$与$S_{l_2}S_{l_2+1}S_{l_2+2} \cdots S_{r_2}$完全相同。
求有多少个满足所有条件的数。
题解
一个朴素的想法是把区间的对应转化为点的对应，然后用并查集把对应的相同的点合并起来，最后答案即为 $9\times 10^{C-1}$，其中 $C$ 为集合个数。
然后你发现集合的合并具有可加性。用倍增的思想，把长为 $L$ 的区间分成若干长度为 $2$ 的幂的区间，创建 $\lfloor \log_2 n\rfloor$ 层并查集，设 $fa(x, k)$ 为以 $x$ 为左端点，长度为 $2^k$ 的区间的那一层并查集的父亲。这样合并就是 $\mathcal{O}(\log n)$ 的。
然后最后我们想看 $k=0$ 的那层并查集有多少个集合，所以下放一下，从第 $k$ 层的对应关系推到第 $k-1$ 层。最后统计答案即可。
#include <bits/stdc++.h>
#define pb emplace_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
inline ll read() {...}
inline void write(ll x) {...}
const int MAX_N = 1e5 + 10, MAX_LOG = 17, MOD = 1e9 + 7;
int n, m, log_2[MAX_N];
void init_log2(int n) {
log_2[1] = 0;
for(int i = 1; i <= n; i++)
log_2[i] = log_2[i >> 1] + 1;
}
struct dsu {
int fa[MAX_N][MAX_LOG];
dsu(int n) {
for(int i = 1; i <= n; i++)
for(int j = 0; j < MAX_LOG; j++)
fa[i][j] = i;
}
int find(int x, int k) {
if(fa[x][k] == x) return x;
return fa[x][k] = find(fa[x][k], k);
}
void merge(int x, int y, int k) {
int fx = find(x, k), fy = find(y, k);
fa[fx][k] = fy;
}
};
int main() {
n = read(), m = read();
init_log2(n);
dsu D = dsu(n);
for(int i = 1; i <= m; i++) {
int l1 = read(), r1 = read(), l2 = read(), r2 = read();
for(int k = MAX_LOG - 1; k >= 0; k--)
if(l1 + (1 << k) - 1 <= r1) {
D.merge(l1, l2, k);
l1 += (1 << k), l2 += (1 << k);
}
}
for(int k = MAX_LOG - 1; k >= 1; k--)
for(int i = 1; i + (1 << k) - 1 <= n; i++) {
int I = D.find(i, k);
D.merge(i, I, k - 1), D.merge(i + (1 << (k - 1)), I + (1 << (k - 1)), k - 1);
}
ll ans = 1;
for(int i = 1; i <= n; i++)
if(D.fa[i][0] == i) ans = 1ll * ans * (ans == 1 ? 9 : 10) % MOD;
write(ans), putchar('\n');
return 0;
}
♥