形式化题目

有 $n$ 个区间 $[l_i, r_i)$（即覆盖位置 $l_i, l_i+1, \dots, r_i-1$），并且

初始时长度为 $2n+1$ 的序列 $a_0,\dots,a_{2n}$ 全为 $0$。按任意顺序把每个区间恰好执行一次：第 $i$ 个区间把 $a_{l_i},\dots,a_{r_i-1}$ 全部赋成 $i$。要求选择执行顺序，最大化

注意下标从 $0$ 开始，而 $a_0$ 永远不会被任何区间覆盖（因为所有 $l_i \geqslant 1$）。

暴力解法

思路

题意本身就是一个可以照做的过程：$n$ 很小的时候，直接枚举所有 $n!$ 种执行顺序，每种顺序都在数组上真的覆盖赋值一遍，再统计相邻不同的位置数，取最大值即可。

它的价值有两点：一是作为对拍基准，二是能让我们放心地相信后面推出来的公式。做法没有任何取巧，但在 $n \leqslant 8$ 时 $n!$ 还可以接受。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-02 15:23
 * update_at: 2026-10-03 14:28
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
//
// 题意完全照做：枚举 n 个操作的 n! 种执行顺序，每种顺序都真的在数组上
// 从后往前覆盖赋值，然后统计 a_0..a_{2n} 中相邻不同的位置数，取最大值。
// 只适用于 n <= 8 左右，但对拍时它是绝对正确的基准。
#include <bits/stdc++.h>
using namespace std;

const int maxn = 20;

int n;
int lft[maxn], rgt[maxn];
int a[2 * maxn + 5]; // 序列 a_0..a_{2n}
int ord[maxn];       // 当前枚举到的操作顺序

void read_data() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> lft[i] >> rgt[i];
    }
}

// 按 ord 给出的顺序执行操作，返回相邻不同的位置数。
int count_breaks() {
    for (int p = 0; p <= 2 * n; p++) {
        a[p] = 0;
    }
    for (int t = 0; t < n; t++) {
        int id = ord[t];
        for (int p = lft[id]; p < rgt[id]; p++) {
            a[p] = id + 1; // 赋值 i（用 i+1 表示，0 留给初始值）
        }
    }
    int cnt = 0;
    for (int i = 0; i < 2 * n; i++) {
        if (a[i] != a[i + 1]) {
            cnt++;
        }
    }
    return cnt;
}

void solve() {
    for (int i = 0; i < n; i++) {
        ord[i] = i;
    }
    int best = 0;
    do {
        best = max(best, count_breaks());
    } while (next_permutation(ord, ord + n));
    cout << best << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    read_data();
    solve();
    return 0;
}

复杂度

时间复杂度 $O(n! \cdot n)$（每种顺序还要 $O(n)$ 次赋值），空间 $O(n)$。对 $n = 5000$ 完全不可行。

瓶颈

瓶颈显然在于"枚举顺序"这件事本身。但真正值得反思的是：我们真的有 $n!$ 种本质不同的可能吗？

数组的值只由"每个位置最后被谁覆盖"决定。所有区间都覆盖 $l_i$，而没有任何区间覆盖 $l_i - 1$；位置 $r_i - 1$ 被区间 $i$ 覆盖，位置 $r_i$ 不被区间 $i$ 覆盖。也就是说，相邻不同的位置（下面叫"断点"）只可能出现在 $2n$ 个端点处，别的位置必然相等。这提示我们用"每个端点能不能成为断点"来描述问题，答案自然就被压进了 $O(n)$ 个布尔量的范围里。

正解

思路

第一步：把"顺序"翻译成"端点的二选一"。

我们只关心每个端点 $s \in \{1,\dots,2n\}$ 是不是断点（$s$ 是断点定义为 $a_{s-1} \neq a_s$）。由于端点两两不同，$s$ 一定恰好是某一个区间的 $l_j$ 或 $r_j$。讨论 $s$ 处的两个邻居最终被谁写：

• 若 $s = l_j$：最终 $a_s = j$；而 $a_{s-1}$ 等于"在 $j$ 之后（最后一次）写 $s-1$ 的那个区间"，$s-1$ 被 $k$ 覆盖需要 $l_k < s < r_k$。所以

• 若 $s = r_j$：$a_{s-1} = j$（因为 $j$ 覆盖 $s-1$），而 $a_s$ 由最后写 $s$ 的那个区间决定，$s$ 被 $k$ 覆盖同样需要 $l_k < s < r_k$。所以

两类条件的形状完全一样："端点 $s$ 是断点"当且仅当有某个区间 $k$ 覆盖了 $s$（即 $l_k < s < r_k$）并且 $k$ 排在包含 $s$ 的那个区间 $j$ 之后。

特别地，位置 $2n$ 一定是断点：$2n$ 是某个 $r_j$，而 $a_{2n}$ 永远不会被覆盖（$=0$），$a_{2n-1} = j \neq 0$。

第二步：找出真正的冲突——交错区间对。

每次从 $2n$ 个端点里挑若干个作为断点，是一组选择。两组选择之间唯一的约束来自"$k$ 排在 $j$ 之后"这种先后关系本身是不是能同时满足。设两个区间的左端点满足 $l_i < l_j$，分类讨论：

1. $r_i < l_j$：两个区间不相交，先后顺序互不影响，端点 $l_i, l_j, r_i, r_j$ 都能成为断点。

2. $r_j < r_i$：区间 $j$ 被区间 $i$ 包含。把 $i$ 排在前面即可让 $l_j$ 与 $r_j$ 都成为断点，也无冲突。

3. $l_i < l_j < r_i < r_j$：两个区间交错。这时：

   • 若 $l_j$ 要成为断点，就需要区间 $i$ 排在 $j$ 之后（因为只有 $i$ 覆盖 $l_j$）；
   • 若 $r_i$ 要成为断点，就需要区间 $j$ 排在 $i$ 之后（因为只有 $j$ 覆盖 $r_i$）。

   两者不能同时成立。于是得到唯一的冲突：

第三步：建二分图，用 König 定理算答案。

把 $2n$ 个端点分成两类：左部点是所有 $r_i$，右部点是所有 $l_j$。对每个交错对 $l_i < l_j < r_i < r_j$，在 $r_i$ 与 $l_j$ 之间连一条边。上面的结论说：

为什么图上只要有边，冲突就一定来自交错对？ 若存在区间 $k$ 同时覆盖 $r_i$ 与 $l_j$（$l_k < l_j < r_k$ 且 $r_i < r_k$），且 $l_i < l_j$，那么 $l_k < l_j < r_k$ 与 $r_i < r_k$、$l_i < l_j$ 一起恰好给出 $l_i < l_j < r_i < r_k$，也就是 $i, k$ 本身构成一个交错对，$r_i$ 与 $l_j$ 之间本来就有边。所以不必再为"被同一个区间覆盖"单独设约束。

那么答案上界是什么？设最终断点集合为 $B$。取

它的反面是 $B$，而任何一条边 $r_i l_j$ 的两个端点不可能同时落在 $C$ 里（$r_i$ 与 $l_j$ 不能同时被选，所以至少有一个不在 $B$ 里）。因此 $C$ 是一个顶点覆盖，$|C| \geqslant \nu$（$\nu$ 为最大匹配数），于是

第四步：上界可以达到（构造顺序）。

取一个大小恰为 $2n-\nu$ 的独立集 $S$（König 定理保证它存在：由最大匹配的交替路可以构造出最小顶点覆盖 $C$，令 $S = V \setminus C$ 即可）。对 $S$ 建一张有向图 $D_S$：若 $s \in S \cap \{l_j, r_j\}$，且区间 $m$ 覆盖了 $s$（即 $l_m < s < r_m$），就连一条弧

引理：$D_S$ 无环。

反设存在环，取其中长度最小的一个 $j_1 \to j_2 \to \dots \to j_k \to j_1$。对每条弧 $j_{t-1} \to j_t$，取一个见证 $x_t \in S \cap \{l_{j_t}, r_{j_t}\}$ 满足 $l_{j_{t-1}} < x_t < r_{j_{t-1}}$。由 $l_{j_t} \leqslant x_t \leqslant r_{j_t}$ 立刻得到

$$l_{j_{t-1}} < r_{j_t}, \qquad l_{j_t} < r_{j_{t-1}},$$

即环上相邻的两个区间必然相交。取环上 $r_{j_p}$ 最大的那个区间。（$r$ 两两不同，所以它唯一。）

• 环上前驱 $j_{p-1}$ 与 $j_p$ 相交，且 $r_{j_{p-1}} < r_{j_p}$，所以两者嵌套。若 $l_{j_p} < l_{j_{p-1}}$，那就是 $j_{p-1} \subset j_p$，可弧 $j_{p-1} \to j_p$ 的见证必须落在开区间 $(l_{j_{p-1}}, r_{j_{p-1}})$ 内，而 $l_{j_p} < l_{j_{p-1}}$、$r_{j_p} > r_{j_{p-1}}$ 说明 $j_p$ 的两个端点都在这个开区间之外，矛盾。所以只能 $l_{j_{p-1}} < l_{j_p}$，即 $j_{p-1} \supset j_p$。
• 对后继 $j_{p+1}$ 同理：若 $l_{j_p} < l_{j_{p+1}}$，则 $r_{j_{p+1}} < r_{j_p}$（最大性）给出 $j_{p+1} \subset j_p$；若 $l_{j_{p+1}} < l_{j_p}$，则 $j_{p+1} \supset j_p$，弧 $j_p \to j_{p+1}$ 的见证落在 $(l_{j_p}, r_{j_p})$ 内却必须是 $j_{p+1}$ 的端点，也矛盾。所以 $j_p \supset j_{p+1}$。

于是 $j_{p-1} \supset j_p \supset j_{p+1}$，$j_{p-1}$ 覆盖了 $j_{p+1}$ 内含的一切，特别地覆盖了见证 $x_{p+1} \in S$，所以弧 $j_{p-1} \to j_{p+1}$ 存在。把它接进原环就得到一个长度 $k-1$ 的环；$k=2$ 时它直接退化为 $j_{p-1} \supset j_p \supset j_{p-1}$ 的矛盾。无论哪种都与"长度最小"矛盾，故 $D_S$ 无环。

取 $D_S$ 的任意一个拓扑序执行操作：对每个 $s \in S$，覆盖它的区间（如果存在）都排在它所属区间之后，按第一步的判定 $s$ 必然是断点。所以 $|B| \geqslant |S| = 2n - \nu$。

注意这一步只用到"存在性"：代码只需要算 $\nu$，不需要真的输出执行顺序，所以引理只用来说明答案刻度没有缺口。

综合第三、四步：

其中 $\nu$ 是"左部点 $r_i$、右部点 $l_j$，$l_i < l_j < r_i < r_j$ 连边"这张二分图的最大匹配。

样例验证。 样例的区间是 $[2,3),[6,7),[1,9),[5,10),[4,8)$。交错的只有 $[1,9)$ 与 $[5,10)$（$1<5<9<10$），所以二分图只有一条边 $r_{[1,9)} - l_{[5,10)}$，$\nu = 1$，答案 $10 - 1 = 9$，与样例一致。

实现要点。 $n \leqslant 5000$ 时最大匹配可以用匈牙利（找增广路）算法。朴素实现要枚举所有出边，而这里 $E$ 最坏可以达到 $n^2/2 \approx 1.25\times 10^7$，直接跑有超时风险；把邻接矩阵按 $64$ 位压进 unsigned long long，寻找"还没访问过的出边"这一步就变成 adj[u][w] & ~visR[w] 一次跳过一个字，用 __builtin_ctzll 取最低位。这样最坏复杂度 $O(n^3/64)$，实测 $n = 5000$ 的稠密数据约 $0.5$ s。

内存也要小心（题面特意警告了 16 MiB）：压位邻接矩阵是 $\frac{n}{64} \cdot n$ 个 unsigned long long，$n = 5000$ 时约 $3.0$ MiB，可以放心开成全局数组。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-02 15:23
 * update_at: 2026-10-03 14:28
 */
// P9726 [EC Final 2022] Magic
//
// n 个区间 [l_i, r_i)（赋值 i 到位置 l_i..r_i-1），2n 个端点互不相同。
// 任意顺序执行每个区间一次，最大化 a_0..a_{2n} 中相邻不同的位置数。
//
// 模型：位置 i 成为“断点”当且仅当 a_i != a_{i+1}。
//   所有区间都覆盖 l_i，但都不覆盖 l_i-1；位置 r_i-1 被 i 覆盖，r_i 不被 i 覆盖。
//   因此断点只可能出现在 2n 个端点处，且每个端点 s 是否成为断点
//   等价于“把写着 s 的那个区间放到最后”这一件事是否被安排成真。
//
// 关键观察：对相交且不包含的两个区间 l_i < l_j < r_i < r_j，
//   它们不可能同时“在最后写自己的断点”：谁先执行，谁的那一侧端点就被对方覆盖。
//   于是只有 l_i < l_j < r_i < r_j 这样的“交错对”才会产生二选一冲突：
//       选 r_i 当断点  <=>  区间 j 必须排在 i 前面
//       选 l_j 当断点  <=>  区间 i 必须排在 j 前面
//   两者不能同时成立，也就是二分图中“r_i 与 l_j 不能同时被选”。
//
// 把 2n 个端点分成两类：左部点 = 每个区间的 r_i，右部点 = 每个区间的 l_j；
// 若 l_i < l_j < r_i < r_j 则在 r_i 与 l_j 之间连边。
// 那么“可同时当选断点的端点集合”正是这张二分图的一个独立集，
// 答案是 2n - 最大匹配（König 定理：最大独立集 = 总点数 - 最大匹配）。
//   上界方向：设最终断点集合为 B，则 {r_i : r_i 不在 B} ∪ {l_j : l_j 不在 B}
//             是一个大小 2n-|B| 的独立集，故 |B| <= 2n - 最大匹配。
//   可达方向：取最大独立集 S，对每个 s ∈ S 与包含它的区间连有向边
//             （“被覆盖者必须在覆盖者之后执行”），这张图无环，
//             任一拓扑序都能让 S 中所有端点成为断点。
//
// 复杂度：建图 O(n^2)，匈牙利算法 O(n^3/64)（邻接矩阵用 64 位压位），
// 空间 O(n^2/64)。
#include <bits/stdc++.h>
using namespace std;

const int maxn = 5005;
const int maxw = (maxn + 63) / 64;

int n;
int words;                          // 邻接矩阵按 64 位分成的“字”数
int lft[maxn], rgt[maxn];           // 第 i 个区间覆盖位置 [lft_i, rgt_i - 1]
unsigned long long adj[maxn][maxw]; // 二分图：左部点 i（r_i）-> 右部点 j（l_j）
int matchR[maxn];                   // 右部点匹配到的左部点，-1 表示未匹配
int matchL[maxn];                   // 左部点匹配到的右部点，-1 表示未匹配
unsigned long long visR[maxw];      // 本轮匈牙利中右部点的访问标记

// 匈牙利算法：从左侧点 u 出发找增广路。
// 右部点的访问标记按位存储，未访问的候选点 = adj[u] & ~visR，一次能跳过一整字。
bool dfs(int u) {
    for (int w = 0; w < words; w++) {
        unsigned long long cur = adj[u][w] & ~visR[w];
        while (cur) {
            int b = __builtin_ctzll(cur); // 取出最低位的 1
            cur &= cur - 1;               // 抹掉这一位
            visR[w] |= 1ULL << b;
            int v = (w << 6) + b;
            if (matchR[v] == -1 || dfs(matchR[v])) {
                matchR[v] = u;
                matchL[u] = v;
                return true;
            }
        }
    }
    return false;
}

void read_data() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> lft[i] >> rgt[i];
    }
}

void solve() {
    words = (n + 63) / 64;
    // 建图：l_i < l_j < r_i < r_j 时连边 i -> j
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) {
                continue;
            }
            if (lft[i] < lft[j] && lft[j] < rgt[i] && rgt[i] < rgt[j]) {
                adj[i][j >> 6] |= 1ULL << (j & 63);
            }
        }
    }

    for (int i = 0; i < n; i++) {
        matchR[i] = -1;
        matchL[i] = -1;
    }

    int matching = 0;
    for (int i = 0; i < n; i++) {
        if (matchL[i] != -1) {
            continue;
        }
        memset(visR, 0, sizeof(unsigned long long) * words);
        if (dfs(i)) {
            matching++;
        }
    }

    cout << 2 * n - matching << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    read_data();
    solve();
    return 0;
}

复杂度

设 $\nu$ 为最大匹配数。

• 建图：两层循环 $O(n^2)$。
• 匈牙利算法：每个未匹配左侧点跑一次增广路，每次找增广路的代价是 $O(n^2/64)$，共 $n$ 轮，最坏 $O(n^3/64)$；实测 $n = 5000$ 的最坏数据约 $0.5$ s。
• 空间：压位邻接矩阵 $O(n^2/64)$，其余数组 $O(n)$，总计约 $3$ MiB。

总结

• 断点只在端点处。 每个区间都覆盖自己的 $l_i$ 却不覆盖 $l_i - 1$，覆盖 $r_i - 1$ 却不覆盖 $r_i$，所以只有 $2n$ 个端点可能成为断点，问题被压缩成"选哪些端点"。
• 端点成为断点的条件统一。 “$s$ 是断点”$\iff$"某个覆盖 $s$ 的区间排在 $s$ 所属区间之后"，这让"选端点"和"排顺序"互相翻译。
• 冲突只有交错对。 对 $l_i < l_j$ 分类讨论，只有 $l_i < l_j < r_i < r_j$ 会强制 $r_i$ 与 $l_j$ 二选一；其余两类（相离、包含）没有任何约束。
• **答案 = 2n - $ 最大匹配。** 把 $r_i 放左部、$l_j$ 放右部、交错对连边，可选的断点集合正是这张二分图的独立集，“上界 = 独立集 ≤ $2n - \nu$”，而按覆盖关系建出的先后约束图无环，任一拓扑序都能达到 $2n - \nu$（König 定理的直接应用）。
• 实现要压位。 稠密图下朴素的匈牙利太慢，用 unsigned long long 压位邻接矩阵 + __builtin_ctzll 枚举出边，先把空间压进 16 MiB，再把时间压到 $O(n^3/64)$。