题解：AT_abc408_c [ABC408C] Not All Covered

Ashankamiko · 2025-06-01 11:08:10 · 题解

题目简述

题意

给出 N 座编号为 1 到 N 的塔楼，初始为空。有 M 个区间存在炮塔（L_i 到 R_i 之间的炮塔需要叠加），问最少要消灭几个炮塔才能使那个塔楼没有炮塔。

思路

首先是暴力枚举。

• 定义 cnt 数组为每座塔楼的炮塔数量。
• 对于 M 次操作，每次都让 L_i 到 R_i 之间的数全部 +1。
• 最后遍历 N 个塔楼，取出最小的 cnt_i。
• 时间复杂度为 O(N \times (N+M))。

最后的结果也显而易见，参考下图。 所以本题需要这些算法（或更多）才不会超时（按照运行效率排序）：

• 树状数组。
• 线段树。
• 分块。

这里我采用分块解题，分块具有以下特点：

• 思路简单，直观，容易理解。
• 对于数据比较大的，效率往往不高，但足以通过本题。

其实本题的模板便是：P3372 线段树 1，这一题写分块也能过。

这两题的区别在于：

• P3372 是对 x 到 y 之间的所有数加上 k，而这题只需对 x 到 y 之间的数 +1 即可。
• P3372 查询为一整个区间，而这题查询时只需要查询一个数。

那这题不就变的更简单了吗（说白了还是线段树）。

分块

顾名思义，分块就是把一个序列分成多个块，处理这些块的时候就可以统一数据，减少时间的开销。

一般把每个块大小不超过 \lfloor \sqrt{N} \rfloor，共有 \lceil \sqrt{N} \rceil 块，所以时间复杂度为 O((N+M) \times \sqrt{N})。

分块的基础变量

分块所需要的基础变量：

• 用 sum_i 表示第 i 段中，所有数的和。
• 用 add_i 表示第 i 段一整段需要修改的数，相当于对整段进行处理。
• 用 pos_i 表示第 i 个位置属于哪一段，需要初始化。
• 用 L_i 和 R_i 表示每一段开头和末尾的点。

在处理数据的时候，如果是整块，则直接令 add_i \gets add_i+1，否则，就按照暴力枚举的写法处理不是整块的部分，即：令 a_i \gets a_i+1。

同时，我们还需要更新第 i 段的区间和 sum_i。

AC 代码

可以看出，这一题用分块做巅值耗时也仅仅为 339 毫秒。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define in cin
#define out cout
const int N = 1e6 + 5;
int a[N], sum[N], add[N], L[N], R[N], pos[N], n, m, t; //如上所述
void change(int l, int r, int d) { //让l到r之间的数+d（对于本题，d=1）
    int p = pos[l], q = pos[r];
    if (p == q) { //在同一段内
        for (int i = l; i <= r; i++)
            a[i] += d;
        sum[p] += d * (r - l + 1);
    } else { //维护整段
        for (int i = p + 1; i <= q - 1; i++) //对一整段进行处理
            add[i] += d;
        for (int i = l; i <= R[p]; i++) //处理前段
            a[i] += d;
        sum[p] += d * (R[p] - l + 1);
        for (int i = L[q]; i <= r; i++) //处理后段
            a[i] += d;
        sum[q] += d * (r - L[q] + 1); //更新区间和
    }
}
int ask(int l, int r) { //查询l到r的区间
    int p = pos[l], q = pos[r], ans = 0;
    if (p == q) { //同一段内
        for (int i = l; i <= r; i++)
            ans += a[i];
        ans += add[p] * (r - l + 1);
    } else {
        for (int i = p + 1; i <= q - 1; i++) //同理
            ans += sum[i] + add[i] * (R[i] - L[i] + 1);
        for (int i = l; i <= R[p]; i++)
            ans += a[i];
        ans += add[p] * (R[p] - l + 1);
        for (int i = L[q]; i <= r; i++)
            ans += a[i];
        ans += add[q] * (r - L[q] + 1);
    }
    return ans;
}
signed main() {
    in >> n >> m;
    t = sqrt(n); //分块
    //初始化
    for (int i = 1; i <= t; i++)
        L[i] = (i - 1) * sqrt(n) + 1, R[i] = i * sqrt(n);
    if (R[t] < n)
        t++, L[t] = R[t - 1] + 1, R[t] = n;
    for (int i = 1; i <= t; i++)
        for (int j = L[i]; j <= R[i]; j++)
            pos[j] = i, sum[i] += a[j];
    while (m--) { //m个区间
        int l, r;
        in >> l >> r;
        change(l, r, 1); //令这一整个区间都+1
    }
    int minx = INT_MAX;
    for (int i = 1; i <= n; i++) //n座塔楼
        minx = min(minx, ask(i, i)); //取出炮台数量的最小值
    out << minx; //输出答案
    return 0;
}