子任务 A 题解（纯水平染色）

说句实话，我写的题解真的是不如AI。那么作为一个OI选手人类，我们能做的是什么呢？只有如何想出来的思路罢了。所以本篇题解主要注意的是思想过程，以及遇到一道题目时我的反应。

一、首先

1.1 从长题面中提取

看着很长，最关键的是什么呢？那肯定是提炼（说了句废话）。

通过看题，我们可以找到以下关键点：

注意：因为我们只做A，所以我们只需要考虑横的情况

所以最后就变成了：一开始全白，给操作，每次把一行中的 [x1,x2][x_1, x_2] 这个范围变黑。

好的那我们就成功的完成了缩小（是不是很简单）

1.2 看到问题首先想到什么

第一反应：这是一个二维平面染色问题。但操作仅限于水平方向，显然不同行之间没有关系。

可是SAM说禁用显然，这可怎么办，那只能证明了v-v

  • 操作1：染黑第3行的[1,5]
  • 操作2：染黑第5行的[2,4]
  • 第3行的操作会影响第5行吗？显然不会

核心观察：不同行的操作完全独立！每行的染色结果只取决于该行的操作集合。

于是问题转化为： 对每一行，已知若干区间 [x1,x2][x_1, x_2]，求被覆盖的格子总数。

二、那么我们可以想到什么方法呢

提示：首先我们要考虑的是：因为可能出现相同的地方重复染色，所以自然，我们可以想到以下算法

2.1 方法一：暴力法

思路：对每行，创建一个大小为 mm 的布尔数组，遍历每个操作，将对应位置标记为 true，最后统计 true 的数量。

缺点：m≤109m \le 10^9，数组太大，空间爆炸。

暴力

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
// 此方法仅用于理解问题
#include <bits/stdc++.h>
using namespace std;

int main() {
    int c; long long n, m; int q;
    cin >> c >> n >> m >> q;
    
    //空间占用超标
    vector<vector<bool>> board(n + 1, vector<bool>(m + 1, false));
    
    for (int i = 0; i < q; i++) {
        int t; long long x1, y1, x2, y2;
        cin >> t >> x1 >> y1 >> x2 >> y2;
        if (t == 1) {
            for (long long x = x1; x <= x2; x++) {
                board[y1][x] = true;
            }
        }
    }
    
    long long ans = 0;
    for (int y = 1; y <= n; y++) {
        for (long long x = 1; x <= m; x++) {
            if (board[y][x]) ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

2.2 方法二：线段树/树状数组

思路：对每行建立线段树或树状数组，支持区间染色和查询。每次操作调用区间更新，最后查询整行的覆盖长度。

缺点：需要为每行维护一棵线段树，空间复杂度 O(n⋅log⁡m)O(n \cdot \log m) 或需要动态开点，实现复杂且效率低下。

线段

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
#include <bits/stdc++.h>
using namespace std;

struct SegTree {
    int n;
    vector<int> tree, lazy;
    
    SegTree(int _n) {
        n = _n;
        tree.assign(4 * n + 5, 0);
        lazy.assign(4 * n + 5, 0);
    }
    
    void push(int node, int l, int r) {
        if (lazy[node]) {
            tree[node] = (r - l + 1);
            if (l != r) {
                lazy[node * 2] = lazy[node * 2 + 1] = 1;
            }
            lazy[node] = 0;
        }
    }
    
    void update(int node, int l, int r, int ul, int ur) {
        push(node, l, r);
        if (ul > r || ur < l) return;
        if (ul <= l && r <= ur) {
            lazy[node] = 1;
            push(node, l, r);
            return;
        }
        int mid = (l + r) >> 1;
        update(node * 2, l, mid, ul, ur);
        update(node * 2 + 1, mid + 1, r, ul, ur);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }
    
    int query() {
        return tree[1];
    }
};

int main() {
    int c; long long n, m; int q;
    cin >> c >> n >> m >> q;
    
    // 需要为每行建线段树，空间太大
    unordered_map<long long, SegTree*> rowTrees;
    
    for (int i = 0; i < q; i++) {
        int t; long long x1, y1, x2, y2;
        cin >> t >> x1 >> y1 >> x2 >> y2;
        if (t == 1) {
            if (rowTrees.find(y1) == rowTrees.end()) {
                rowTrees[y1] = new SegTree(m);
            }
            rowTrees[y1]->update(1, 1, m, x1, x2);
        }
    }
    
    long long ans = 0;
    for (auto& p : rowTrees) {
        ans += p.second->query();
    }
    cout << ans << endl;
    return 0;
}

<-本代码由AI辅助生成->

2.3 方法三：区间合并法

思路：将每行的所有区间收集起来，排序后合并重叠或相邻的区间，直接计算并集长度。
那这个就是最后的代码了，直接看下面把

三、区间合并法

3.1 整体流程

1.读入
将水平操作（t=1t=1），存入数组 seg[]。

2.排序
按行号h对 seg[] 排序，使同一行的区间连续。

3.逐行处理
对每一行执行：

  1. 将该行所有区间复制到临时数组 tmp[]
  2. 按左端点l对 tmp[] 排序
  3. 合并扫描：
    • 维护当前区间 [curL, curR]
    • 遍历排序后的区间 [L, R]：
      • 如果 L <= curR + 1：可合并，curR = max(curR, R)
      • 否则：结算当前区间，ans += curR - curL + 1，重置 [curL, curR] = [L, R]
    • 遍历结束后再结算最后一个区间

是不是简单高效的方法呢～

复杂度分析

  • 时间：主要开销是排序。按行号排序 O(cntlog⁡cnt)O(cnt \log cnt)，每行内部排序的总长度不超过 cntcnt，故整体 O(qlog⁡q)O(q \log q)。
  • 空间：两个大小为 qq 的静态数组 seg[] 和 tmp[]，空间 O(q)O(q)。

CODE

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
#include <bits/stdc++.h>
using namespace std;

struct QD {
    long long h;//行号
    long long l;//左端点
    long long r;//右端点
};

QD seg[100005];
QD tmp[100005];

// 按行号排序
bool cmp1(const QD& x, const QD& y) {
    return x.h < y.h;
}
// 按左端点排序
bool cmp2(const QD& x, const QD& y) {
    return x.l < y.l;
}

int main() {
    int c; 
    cin >> c;
    
    long long n, m;
    int q;
    cin >> n >> m >> q;
    
    int cnt = 0;
    for (int i = 0; i < q; i++) {
        int t; long long x1, y1, x2, y2;
        cin >> t >> x1 >> y1 >> x2 >> y2;
        if (t == 1) {
            seg[cnt++] = {y1, x1, x2};
        }
    }
    
    //按行号排序，让同一行的区间连续
    sort(seg, seg + cnt, cmp1);
    
    long long ans = 0;
    
    //遍历每一行
    for (int i = 0; i < cnt; ) {
        int j = i;
        // 找到同一行的区间，j指向下一行的开头
        while (j < cnt && seg[j].h == seg[i].h) {
            j++;
        }
        
        //按左端点排序
        int len = j - i;
        for (int k = 0; k < len; k++) {
            tmp[k] = seg[i + k];
        }
        sort(tmp, tmp + len, cmp2);
        
        //合并区间并累加长度
        long long curL = tmp[0].l;
        long long curR = tmp[0].r;
        for (int k = 1; k < len; k++) {
            long long L = tmp[k].l;
            long long R = tmp[k].r;
            if (L <= curR + 1) {//可合并
                if (R > curR) curR = R;
            } else {//不能合并，结算
                ans += curR - curL + 1;
                curL = L;
                curR = R;
            }
        }
        ans += curR - curL + 1;//别忘了最后一个区间
        
        i = j;// 跳到下一行
    }
    
    cout << ans << endl;
    return 0;
}

🎌 结语

OK啊，分拿到了。本题解结束

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

快来参与讨论吧~