B. Add One 3

有两个 sub task:

  1. 如何确定 [l,r][l, r] 能否成为唯一的 MSS
  2. 最少需要几步
判断问题

先来回答第一个问题。因为我们只能对某个数 +1+1，所以对于一段区间来说，其和只能增大不能减少。考虑和 [l,r][l,r] 邻接的前缀和后缀（即 [i,l−1][i,l-1] 和 [r+1,j][r+1,j] 这两类区间），如果这两类区间的和 ≥0\ge 0，那么我们完全可以把 [l,r][l,r] 接上这个 subrange，这样 ∑[i,r]≥∑[l,r]\sum [i,r]\ge\sum [l,r] 或者 ∑[l,j]≥∑[l,r]\sum [l,j]\ge \sum [l,r]，这就意味着 [l,r][l,r] 永远不可能单独成为 MSS.

方案数

接下来处理最少需要几步。因为整个段需要是唯一的 MSS：

  • 如果 [l,r][l,r] 的某个前缀和小于等于零，即 ∃k,∑i=lkai≤0\exists k,\sum_{i=l}^k a_i\le 0，那么我们完全可以扔掉这个前缀，剩下的部分 [k+1,r][k+1,r] 可以组成 sum 更大的 MSS。这就意味着所有前缀都必须 >0\gt 0
  • 类似的，[l,r][l,r] 的所有后缀也都必须是 >0\gt 0.
  • 同时，考虑不在 [l,r][l,r] 区间的 MSS，设最大的 MSS 为 MM。如果存在这样的 MSS（不在 [l,r][l,r] 里而其和仍为 MM），那么 [l,r][l,r] 至少需要达到 M+1M+1.

所以，我们找两个下标 p1<p2p_1\lt p_2 使得 [l,p1][l,p_1] 这个前缀与 [p2,r][p_2,r] 这个后缀都是负数（也可以是只有负数前缀而没有后缀，或者只有后缀没有前缀）

一个疑惑点是：难道没有可能前缀 [l,p1][l,p_1] 和后缀 [p2,r][p_2,r] 有重叠吗？这种情况下，显然只可能是 [p1,p2][p_1,p_2] 为负数，且绝对值比较大，而 [l,p1][l,p_1] 可正可负。这时，我们可以把这类情况归类到无负前缀或者前后缀均负的分类里。

所以，我们找到负数绝对值最大的前缀与后缀，先将其 +1+1 填成 00 后，还需要再 +1+1 填成 11，也就是说要

max⁡p1,p2∈[l,r]−∑i=lp1ai−∑i=p2rai+C \max_{p_1,p_2\in [l,r]} -\sum_{i=l}^{p_1} a_i -\sum_{i=p_2}^{r} a_i+C

为什么只需要找绝对值最大的前缀 p1p_1 呢？因为就算还有 j<p1j\lt p_1 它的前缀是负数 x=∑[l,j]<∑[l,p1]x=\sum [l,j]\lt \sum[l,p_1]，我们可以先在 ∑[l,j]\sum [l,j] 里加上 xx，然后再把剩下的 +1+1 加到 [l,p1][l,p_1] 上。

这里的 +C+C 是这样算的：如果有非负的前缀与非负后缀，则 +2+2；若只有其一，则只 +1+1。

然后一个变形是，把这里代表前后缀的 ∑\sum 换成代表 [l,r][l,r] 内最大子段和的形式：

max⁡p1,p2(−∑i=lrai+∑i=p1+1p2−1ai+C) \max_{p_1,p_2}\Big( -\sum_{i=l}^r a_i + \sum_{i=p_1+1}^{p_2-1} a_i + C\Big)

对于 MSS 不在 [l,r][l,r] 的情况来说，我们要把 [l,r][l,r] 补到 M+1M+1，所以次数为 M+1−∑i=lrai\boxed{M+1-\sum_{i=l}^r a_i}

所以，总结一下就是：

  • 当没有非负前后缀时，就只用考虑 MSS 在 [l,r][l,r] 外的情况 M+1−∑i=lraiM+1-\sum_{i=l}^r a_i
  • 当只有非负前缀的时候，就需要考虑
    1. MSS 在 [l,r][l,r] 外 M+1−∑i=lraiM+1-\sum_{i=l}^r a_i
    2. 把自己的非负后缀都填到 >0\gt 0，次数为 −∑[p2,r]+1-\sum [p_2,r]+1
  • 当只有非负前缀时是类似的
  • 当有非负前后缀时，四种情况都要考虑。

可以使用线段树维护区间的 MSS、最负后缀、最负前缀，时间复杂度 O(nlog⁡n)O(n\log n).

Code

我的代码里实现方式是不分类讨论，直接对四种情况取 max⁡\max. 可以这样做的原因是因为，四种式子分别对应满足各自情况时需要的最少次数，那么要满足所有情况，就得取其中最大的次数。

例如，如果 [l,r][l,r] 之间没有非负前后缀，这就说明对于“无非负前缀”、“无非负后缀”这两个判定条件我只需要花 00 步，但是又有 MSS 不在 [l,r][l,r] 里，所以需要把 x>0x\gt 0 步把 [l,r][l,r] 补到 M+1M+1，所以最终需要 xx 步。

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
118
119
120
121
122
123
124
125
126
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
using ll         = long long;
using vi         = std::vector<int>;
constexpr ll inf = 1e18;

struct Node {
    ll sum{0};
    ll max_psum{-inf};
    ll max_ssum{-inf};
    ll min_psum{inf};
    ll min_ssum{inf};
    ll max_inseg_sum{-inf};
    int l, r, segl, segr, suf, prf;

    void set(ll x, int pos) {
        sum           = x;
        max_psum      = x;
        max_ssum      = x;
        max_inseg_sum = x;
        min_ssum      = x;
        min_psum      = x;
    }
};

void run() {
    int n, q;
    std::cin >> n >> q;

    vi a(n + 1);
    for (int i = 1; i <= n; i++) std::cin >> a[i];

    std::vector<Node> T(6 * n);

    auto up = [&](Node l, Node r) {
        Node t;
        t.sum = l.sum + r.sum;

        t.max_psum      = std::max(l.max_psum, l.sum + r.max_psum);
        t.max_ssum      = std::max(r.max_ssum, r.sum + l.max_ssum);
        t.max_inseg_sum = std::max({l.max_inseg_sum, r.max_inseg_sum, l.max_ssum + r.max_psum});
        t.min_psum      = std::min(l.min_psum, l.sum + r.min_psum);
        t.min_ssum      = std::min(r.min_ssum, r.sum + l.min_ssum);

        return t;
    };

    auto build = [&](auto F, int p, int l, int r) -> void {
        if (l == r) {
            T[p].set(a[l], l);
            return;
        }
        int mid = l + ((r - l) >> 1);
        F(F, 2 * p, l, mid), F(F, 2 * p + 1, mid + 1, r);
        T[p] = up(T[p * 2], T[p * 2 + 1]);
    };
    build(build, 1, 1, n);

    auto query = [&](auto F, int p, int l, int r, int ql, int qr, bool debug = false) -> Node {
        if (qr < ql) return Node(); // empty range

        if (ql <= l && r <= qr) return T[p];
        int mid = l + ((r - l) >> 1);
        Node res;
        if (qr <= mid) res = F(F, 2 * p, l, mid, ql, qr, debug);
        else if (ql > mid) res = F(F, 2 * p + 1, mid + 1, r, ql, qr, debug);
        else {
            Node left  = F(F, 2 * p, l, mid, ql, mid, debug);
            Node right = F(F, 2 * p + 1, mid + 1, r, mid + 1, qr, debug);
            res        = up(left, right);
        }
        return res;
    };

    auto q1 = [&](int L) {
        if (L == 1) return true;
        else {
            Node t = query(query, 1, 1, n, 1, L - 1);
            return t.max_ssum < 0 /* max suffix sum of [1, l-1] < 0 */;
        }
    };
    auto q2 = [&](int R) {
        if (R == n) return true;
        else {
            Node t = query(query, 1, 1, n, R + 1, n);
            return t.max_psum < 0 /* max prefix sum of [r+1, n] < 0 */;
        }
    };

    Node maxx = query(query, 1, 1, n, 1, n);
    // std::cerr << "global max subarray sum=" << maxx.max_inseg_sum << "\n";

    while (q--) {
        int ql, qr;
        std::cin >> ql >> qr;
        bool b1 = q1(ql), b2 = q2(qr);
        if (!b1 || !b2) {
            std::cout << "-1\n";
            continue;
        }

        Node t     = query(query, 1, 1, n, ql, qr);
        auto mid   = query(query, 1, 1, n, ql + 1, qr - 1);
        Node lf    = query(query, 1, 1, n, 1, ql - 1);
        Node rf    = query(query, 1, 1, n, qr + 1, n);
        ll outside = std::max({lf.max_inseg_sum, rf.max_inseg_sum, 0ll});

        if (ql == qr) {
            std::cout << std::max(0ll, outside - a[ql] + 1) << "\n";
            continue;
        }

        ll ans = std::max(0ll, mid.max_inseg_sum) - t.sum + 2; // mss in (l, r)
        ans    = std::max({ans, 1 - t.min_psum, 1 - t.min_ssum, outside - t.sum + 1});
        // no prefix <= 0, no suffix <= 0, mss outside [l,r]
        std::cout << std::max(0ll, ans) << "\n";
    }
}

int main() {
    int T;
    std::cin >> T;
    while (T--) run();
}

C. Iridescent Universe

考虑图，如果一个点出发的所有边都有相同的 target color，那么我们可以先随便染色其他边，最后再染色这个点，那么我们就不需要理睬这个点的 indicent edge 之前是什么颜色的。

用第一个样例来解释，我们不管之前到底是怎么染色的，只要最后一次染色是 22 号点染色 22 号颜色，那么最后的图里，22 出发的所有边一定都是 22 号颜色。

所以我们可以拓扑排序：每次染色点，其 incident edges 都有相同的 target color，然后删边。最后如果还有边留下来，那么我们检查他们的 target color 和 initial color 匹配即可。

Code

我这里使用 map<int, int> 记录每个点的边的颜色信息。时间复杂度是 O(nlog⁡n)O(n\log 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
68
69
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <utility>
#include <vector>
using vi        = std::vector<int>;
constexpr int N = 2e5 + 5;

struct edge {
    int uv, c, tc;
    int colored;
} E[N];

vi G[N];
std::map<int, int> C[N];
int vis[N];

int main() {
    int n, m, k;
    std::cin >> n >> m >> k;
    for (int i = 0, u, v, c, t; i < m; i++) {
        std::cin >> u >> v >> c >> t;
        E[i] = {u ^ v, c, t, false};
        G[u].push_back(i), G[v].push_back(i);
        C[u][t]++, C[v][t]++;
    }

    std::queue<int> q;
    std::vector<std::pair<int, int>> ans;
    for (int i = 1; i <= n; i++)
        if (C[i].size() == 1) q.push(i), vis[i] = true;

    int cnt = 0;
    while (!q.empty()) {
        int u = q.front();
        ans.push_back({u, C[u].begin()->first});
        for (auto eid : G[u]) E[eid].colored = true;
        cnt++;
        q.pop();

        for (int eid : G[u]) {
            int v = E[eid].uv ^ u;
            if (vis[v]) continue;

            C[v][E[eid].tc]--;
            if (C[v][E[eid].tc] == 0) C[v].erase(E[eid].tc);

            if (C[v].size() == 1) {
                q.push(v);
                vis[v] = true;
            }
        }
    }

    if (cnt != n) {
        for (int eid = 0; eid < m; eid++) {
            if (E[eid].colored) continue;
            if (E[eid].c != E[eid].tc) {
                std::cout << "-1\n";
                return 0;
            }
        }
    }

    std::reverse(ans.begin(), ans.end());
    std::cout << ans.size() << "\n";
    for (auto &[u, c] : ans) std::cout << u << " " << c << "\n";
}

E. Omniscient Artist

矩形覆盖数点会联想到扫描线：按 xx 递增扫描矩形，同时用数据结构维护 yy 轴找到符合条件的点。所以，我们把矩形的左右两边加入扫描线，左侧边 +1+1 表示从这个 xx 坐标开始 [y1,y2][y_1,y_2] 之间的点会多出现 11；右侧边 −1-1.

那么我们“维护 yy 轴”，想要维护的是什么呢？其实是 map[x] = y，意义为有 yy 个点出现 xx 次。这样，我们就可以遍历 cmcm，快速加和点数。

我们怎么维护这个东西呢？线段树并不好做，这个东西维护起来很怪，所以我们使用分块. 块上维护区间加的 tag（注意查询 cmcm 的时候也要考虑这个 tag），和一个 unordered_map（其实建议用数组而不是 unordered_map）

但是如果直接查询 cmcm 的话，时间复杂度是错的，因为枚举 cmcm 需要 O(n/m)O(n/m)，还需要枚举第几块 O(n)O(\sqrt n)，总共 nn 轮，时间复杂度是 O(n2nm)O(\frac{n^2\sqrt n}{m}) 可能变成 O(n2)O(n^2).

min⁡,max⁡\min,\max 优化上下界

我们给每一个块额外维护 min⁡,max⁡\min,\max 分别表示最少出现几次、最多出现几次，然后查询时枚举块，cc 的范围由 min⁡,max⁡\min,\max 决定。这样，单轮查询的时间复杂度就从 O(nnm)O(\frac{n\sqrt n}{m}) 降为 O(nm)O(\frac{n}{m})

为什么这样子做会降低复杂度呢？我们考察每一次区间操作对于区间 max⁡i−min⁡i\max_i-\min_i 的影响。每一次区间操作会横跨 xx 个完整的区间，以及最多 22 个散块。

如果对于整个块都 +1/−1+1/-1 的话，其 max⁡−min⁡\max-\min 不变，因为两者会同步变化。对于散块而言，这个散块所属的整块，其 max⁡−min⁡\max-\min 最多 +1/−1+1/-1。

因此，每一次区间操作使得 ∑imax⁡i−min⁡i\sum_{i} \max_i-\min_i 最多增加 22，故 nn 次区间操作使得这个和式 ≤2n\le 2n，即 O(n)O(n).

Code

一个实现上的细节：我第一版代码是对 xx 坐标 sort 之后，进行扫描线，先更新点集后，选择用 x - prevX 计算宽（和计算矩形的面积那样）

但是这个问题就在于，如果是先加入线段再统计点数，那么刚加进来的线段覆盖的点 (xi,yi)(x_i,y_i) 会有 p+1p+1 次 occurrance，而在其左侧 yy 坐标相同的点却只出现了 pp 次。

错误代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
prvX = scan[0].x-1;
for (int i = 0, j; i < scan.size();) {
    // 统计答案
    int x   = scan[i].x;
    int len = x - prvX;
    j       = i;

    while (j < scan.size() && scan[j].x == scan[i].x) {
        add(scan[j].lb, scan[j].ub, scan[j].exit);
        j++;
    }

    for (int b = 1; b <= blocks; b++) {
        for (int c = std::max(1, (min[b] + m - 1) / m); c * m <= max[b]; c++) {
            if (c * m < block_add[b]) continue;
            i64 cnt = cntpoint[b][c * m - block_add[b]];
            ans[c] += cnt * len;
        }
    }

    prvX = x;
    i    = j;
}

所以，一个代码难度更小的做法是，直接让 xx 从 11 到 nn 递增，且只处理横座标为 xx 的线段，在分块上维护。维护完后统计点数。这样，查询的时间复杂度是 O(n2m)O(\frac{n^2}{m})，也不会 TLE.

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
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iostream>
#include <vector>
constexpr int N = 3e5 + 5;
constexpr int B = 600;
using i64       = long long;

struct Rec {
    int l, r, t, b;
} r[N];
struct Seg {
    int x, ub, lb, exit, id;
};
int n, m;
std::vector<Seg> scan[N];

int blocksize, blocks;
int bid[N], bl[B], br[B];
int cnty[N], prvX{-1}, block_add[B], max[B], min[B];
int cntpoint[B][N];
i64 ans[B];

void rebuild(int l, int r, int w) {
    assert(bid[l] == bid[r]);
    int id = bid[l];

    for (int i = bl[id]; i <= br[id]; i++) cntpoint[id][cnty[i]]--;
    max[id] = 0, min[id] = N;
    for (int i = bl[id]; i <= br[id]; i++) {
        cnty[i] += block_add[id];
        if (l <= i && i <= r) cnty[i] += w;
        cntpoint[id][cnty[i]]++;
        max[id] = std::max(max[id], cnty[i]);
        min[id] = std::min(min[id], cnty[i]);
    }
    block_add[id] = 0;
}

void add(int l, int r, int w) {
    if (bid[l] == bid[r]) rebuild(l, r, w);
    else {
        rebuild(l, br[bid[l]], w);
        for (int i = bid[l] + 1; i <= bid[r] - 1; i++) block_add[i] += w, max[i] += w, min[i] += w;
        rebuild(bl[bid[r]], r, w);
    }
}

void debug() {
    for (int b = 1; b <= blocks; b++) {
        std::cerr << "Block " << b << ": \n";
        for (int i = bl[b]; i <= br[b]; i++) std::cerr << "\tPos " << i << " = " << cnty[i] + block_add[b] << "\n";
        for (int cnt = 0; cnt <= max[b]; cnt++) {
            if (cntpoint[b][cnt] == 0) continue;
            std::cerr << "\tCount " << cnt + block_add[b] << ": " << cntpoint[b][cnt] << " points\n";
        }
    }
}

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    std::cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        std::cin >> r[i].l >> r[i].r >> r[i].b >> r[i].t;
        r[i].t--;
        scan[r[i].l].push_back({r[i].l, r[i].t, r[i].b, 1, i});
        // scan.push_back({r[i].r - 1, r[i].t, r[i].b, 0, i});
        scan[r[i].r].push_back({r[i].r, r[i].t, r[i].b, -1, i});
    }

    // blocks
    blocksize = (int)std::sqrt(n);
    for (int i = 1; i <= n; i++) bid[i] = (i - 1) / blocksize + 1;
    for (int i = 1; i <= bid[n]; i++) {
        bl[i] = (i - 1) * blocksize + 1;
        br[i] = i * blocksize;
    }
    br[bid[n]] = n, blocks = bid[n];
    for (int b = 1; b <= blocks; b++) {
        cntpoint[b][0] = br[b] - bl[b] + 1;
        max[b] = 0, min[b] = 0;
    }

    for (int i = 1; i <= n; i++) {
        for (auto [x, ub, lb, v, id] : scan[i]) add(lb, ub, v);

        for (int b = 1; b <= blocks; b++) {
            for (int c = std::max(1, (min[b] + m - 1) / m); c * m <= std::min(n, max[b]); c++) {
                if (c * m < block_add[b]) continue;
                ans[c] += (i64)cntpoint[b][c * m - block_add[b]];
            }
        }
    }

    for (int c = 1; c * m <= n; c++) std::cout << ans[c] << "\n";
}

F. Witnessing the Miracle

这个题本质上是两个序列之间进行匹配，即考虑 sis_i 最终状态下能否和 tjt_j 进行匹配。

不过，由于题目有“移除 kk 个磁铁”的设定，实际上，对于某一个 sis_i，假设其左边激活 dd 个磁铁，那么其在 tt 序列里对应的位置是可以唯一确定的：j=i+d−(k−d)j=i+d-(k-d).

我们令 dp 状态为 dp[i,d]dp[i,d] 表示在 s[1,i−1]s[1,i-1] 中间激活 dd 个磁铁的方案数量. 那么我们就考虑怎么从 dp[i−1]dp[i-1] 转移到 dp[i]dp[i] 上.

考虑 sis_i 和 tjt_j 各自可以填什么数字：

  • 如果 si=0,tj=0s_i=0,t_j=0，可行。

    都没有磁铁的位置显然可以互相匹配，所以 dp[i, d] += dp[i-1, d]

  • 如果 si=0,tj=1s_i=0, t_j=1，不可行

    原来没有磁铁不可能凭空出现磁铁（就算有，那也是从 ss 的其他地方跑过来的），所以不更新 dp

  • 如果 si=1,tj=1s_i=1,t_j=1，可行

    有磁铁的位置匹配有磁铁的位置，说明这块磁铁没有被激活，dp[i, d] += dp[i-1, d]

  • 如果 si=1,tj=0s_i=1,t_j=0，可行

    有磁铁的位置最终匹配到没有磁铁的位置，说明这块磁铁被激活了，dp[i, d+1] += dp[i-1, d]

这个 dp 乍一看比较难懂。实际上真的比较难懂。我建议还是按 dp[i,j]dp[i,j] 的思路来看

最后的答案即为 dp[n, k].

G. Addition, Multiplication with a Sugar

首先，肯定先把开头的一连串 11 和结尾的一连串 11 拿走，他们一定是加起来的。

然后考虑中间的一段，先看成

x1:≠11×ax2:≠11×b… \boxed{x_1:\ne 1}\boxed{1\times a}\boxed{x_2:\ne 1}\boxed{1\times b}\dots

如果切开更优，则有

∑xi+n>∏xin+1>∏(xi−1) \begin{aligned} \sum x_i+n&\gt \prod x_i\\ n+1&\gt \prod (x_i-1) \end{aligned}

M. Under the Epilogue

我们先来考察题目的性质：因为对于某个点集 SS，我们希望能找到一个点 uu，使得其可以经过 SS 内的每个点，最后回到 uu。我们可以证明，这样的 SS 一定是一个强连通分量。

这是因为，考虑 SS 内的任意两个点 a,ba,b，因为 u→uu\to u 的路径上必定会有下面两种情况中的一个：

  • u→a→b→uu\to a\to b\to u，这是就有 a→ba\to b 的路径了
  • u→b→a→uu\to b\to a\to u，此时，我们可以让 a→u→ba\to u\to b

所以，SS 一定是强连通分量，而且是导出子图。因此，我们的任务就是：给定边集，求出强连通导出子图的数量。考虑到 n≤50n\le 50，开始往 dp 的方向上想。如果用 dp[...] 表示最终答案 SS 的数量，该怎么设计状态呢？

到目前为止，我们只利用了 SS 的性质（从题目定义出发推出的），还没有利用 [li,ri][l_i,r_i] 是连续区间这个性质. 先从简单例子入手思考一下：

首先，只有一个点显然是 SCC. 接着考虑两个点的情况，一定是 a→b,b→aa\to b, b\to a 都有边才行.

接着考虑三个点的情况，我们假定 a<b<ca\lt b\lt c，首先，绝对不可能出现导出子图里三个点出度均为 11 的情况，即 a→b→c→aa\to b\to c\to a. 这是因为如果 cc 可以到 aa，由于 [lc,rc][l_c,r_c] 是连续的，所以 c→bc\to b 这条边一定存在，因此，任意的三个点里，一定存在两个点，他们组成的点集 S2S_2 也是满足条件的 SS.

所以，所有的 S:∣S∣=3S:|S|=3 可以看成是 S:∣S∣=2S:|S|=2 的 S2[i]={ a,b },a<bS_2[i] = \set{a,b},a\lt b 再加上一个点 cc，而且这个点 c∉[a,b]c\notin [a,b]（证明和上一段类似，也是利用 [li,ri][l_i,r_i] 的连续性）.

所以，cc 和 { a,b }\set{a,b} 之间必有连边，即 max⁡(ra,rb)≥c\max(r_a,r_b)\ge c（a/ba/b 向 cc 连一条边）并且 lc≤bl_c\le b（cc 向 a/ba/b 连一条边，lcl_c 至少要比 bb 靠左）.

这个结论可以推广一下，考虑任意两个 vertex set S1,S2S_1, S_2 合并的判定条件：

min⁡i∈S2ai≤max⁡i∈S1bi\min_{i\in S_2}a_i\le \max_{i\in S_1}b_i
也就是两个连通块之间可以互相一步到达。

但是如果单纯是这个条件的话，还是比较难统计. 我们这里作出的一个等价限制是：S=∪i[xi,yi]S=\cup_i [x_i,y_i] 其中 lyi≤yi−1l_{y_i}\le y_{i-1}. 这是因为，如果 uu 要能走回 uu 且 SS 里有比 uu 小的元素，那么无论如何 uu 都应该可以走到某个 v<uv\lt u 的位置上，就可以让 yi−1=v,yi=uy_{i-1}=v, y_i=u.