详细题解.最多涂色次数

区间覆盖最大次数问题：多解法对比与完整思路
问题分析
题目要求我们找到数轴上所有整数点中被闭区间覆盖的最大次数。这是一个经典的区间操作问题，有多种解法，每种解法在时间复杂度、空间复杂度和实现难度上各有优劣。

方法一：差分数组法（最优解）
思路解析
核心思想：利用差分数组高效处理区间更新操作
步骤：
创建一个差分数组 d，初始化为0
对于每个区间 [l, r]，执行 d[l]++ 和 d[r+1]--
遍历差分数组，计算前缀和，前缀和的最大值即为答案

代码实现（C++）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    const int MAX = 1e6 + 2; // 考虑r+1的情况
    vector<int> d(MAX, 0);
    
    for (int i = 0; i < n; ++i) {
        int l, r;
        cin >> l >> r;
        d[l]++;
        if (r + 1 < MAX) {
            d[r + 1]--;
        }
    }
    
    int max_cnt = 0, current = 0;
    for (int i = 0; i < MAX; ++i) {
        current += d[i];
        if (current > max_cnt) {
            max_cnt = current;
        }
    }
    
    cout << max_cnt << endl;
    return 0;
}

复杂度分析
时间复杂度 空间复杂度 优势 劣势
O(n + M) O(M) 实现简单，效率最高 需要知道最大可能的坐标范围
其中，n是区间数量，M是坐标的最大值

方法二：事件点排序法
思路解析
核心思想：将区间的起点和终点转化为事件点，排序后扫描
步骤：
创建事件点数组，每个区间对应两个事件：(l, +1)和(r+1, -1)
对事件点按坐标排序
扫描事件点，维护当前覆盖次数，记录最大值
代码实现（C++）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<pair<int, int>> events;
    events.reserve(2 * n);
    
    for (int i = 0; i < n; ++i) {
        int l, r;
        cin >> l >> r;
        events.emplace_back(l, 1);
        events.emplace_back(r + 1, -1);
    }
    
    sort(events.begin(), events.end());
    
    int max_cnt = 0, current = 0;
    for (const auto& e : events) {
        current += e.second;
        if (current > max_cnt) {
            max_cnt = current;
        }
    }
    
    cout << max_cnt << endl;
    return 0;
}

复杂度分析
时间复杂度 空间复杂度 优势 劣势
O(n log n) O(n) 不需要知道最大坐标范围，适用于稀疏数据 排序带来额外时间开销

方法三：暴力枚举法（不推荐）
思路解析
核心思想：直接统计每个整数点的覆盖次数
步骤：
创建数组记录每个点的覆盖次数
对于每个区间，遍历区间内的所有点并递增计数
遍历数组找到最大值
代码实现（C++）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    const int MAX = 1e6 + 1;
    vector<int> cnt(MAX, 0);
    
    for (int i = 0; i < n; ++i) {
        int l, r;
        cin >> l >> r;
        for (int j = l; j <= r; ++j) {
            cnt[j]++;
        }
    }
    
    int max_cnt = 0;
    for (int i = 0; i < MAX; ++i) {
        if (cnt[i] > max_cnt) {
            max_cnt = cnt[i];
        }
    }
    
    cout << max_cnt << endl;
    return 0;
}

复杂度分析
时间复杂度 空间复杂度 优势 劣势
O(n*L) O(M) 直观易懂 效率极低，仅适用于小数据范围
其中L是区间的平均长度

方法四：线段树法（进阶解法）
思路解析
核心思想：使用线段树维护区间更新和最大值查询
步骤：
构建线段树，支持区间加法和区间最大值查询
对每个区间执行区间加1操作
查询整个区间的最大值
代码实现（C++）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX = 1e6 + 1;

struct SegmentTree {
    struct Node {
        int max_val;
        int lazy;
    };
    
    vector<Node> tree;
    int n;
    
    SegmentTree(int size) {
        n = 1;
        while (n < size) n <<= 1;
        tree.resize(2 * n, {0, 0});
    }
    
    void push(int node, int l, int r) {
        if (tree[node].lazy != 0) {
            tree[node].max_val += tree[node].lazy;
            if (l != r) {
                tree[2*node].lazy += tree[node].lazy;
                tree[2*node+1].lazy += tree[node].lazy;
            }
            tree[node].lazy = 0;
        }
    }
    
    void update_range(int ul, int ur, int val, int node=1, int l=0, int r=-1) {
        if (r == -1) r = n-1;
        push(node, l, r);
        
        if (ur < l || ul > r) return;
        if (ul <= l && r <= ur) {
            tree[node].lazy += val;
            push(node, l, r);
            return;
        }
        
        int mid = (l + r) / 2;
        update_range(ul, ur, val, 2*node, l, mid);
        update_range(ul, ur, val, 2*node+1, mid+1, r);
        tree[node].max_val = max(tree[2*node].max_val, tree[2*node+1].max_val);
    }
    
    int query_max(int ql=0, int qr=-1, int node=1, int l=0, int r=-1) {
        if (r == -1) r = n-1;
        push(node, l, r);
        
        if (qr < l || ql > r) return 0;
        if (ql <= l && r <= qr) {
            return tree[node].max_val;
        }
        
        int mid = (l + r) / 2;
        int left = query_max(ql, qr, 2*node, l, mid);
        int right = query_max(ql, qr, 2*node+1, mid+1, r);
        return max(left, right);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    SegmentTree st(MAX);
    
    for (int i = 0; i < n; ++i) {
        int l, r;
        cin >> l >> r;
        st.update_range(l, r, 1);
    }
    
    cout << st.query_max() << endl;
    return 0;
}

复杂度分析
时间复杂度 空间复杂度 优势 劣势
O(n log M) O(M) 功能强大，支持更复杂的区间操作 实现复杂，常数因子大

方法对比与选择建议
方法 时间复杂度 空间复杂度 适用场景
差分数组法 O(n + M) O(M) 坐标范围已知且不大
事件点排序法 O(n log n) O(n) 坐标范围未知或很大
暴力枚举法 O(n*L) O(M) 数据范围很小
线段树法 O(n log M) O(M) 需要支持复杂区间操作

最优选择建议
如果坐标范围已知且不大（如本题中r≤1e6），差分数组法是最优选择，实现简单且效率最高
如果坐标范围未知或很大，事件点排序法更合适，空间复杂度更低
线段树法适合需要支持更复杂操作的场景，如动态添加区间或多次查询
暴力枚举法仅适用于非常小的数据范围，实际竞赛中不推荐使用
举一反三：类似问题与扩展
区间覆盖点问题：选择最少的点，使得每个区间至少包含一个点
区间完全覆盖问题：选择最少的区间，完全覆盖指定线段
区间不相交问题：选择最多的不相交区间
区间染色问题：计算被染色的总长度
这些问题都可以使用贪心算法或线段树等数据结构解决，核心思路都是对区间进行排序或转换为事件点处理。

下一步建议
尝试解决以下类似问题来巩固所学知识：

给定n个区间，选择最少的点，使得每个区间至少包含一个点
给定n个区间，计算这些区间总共覆盖的长度
给定n个区间，找出所有被覆盖至少k次的点