本文写于 2020年02月14日,距今已超过 1 年,距 2020年03月26日 的最后一次修改也已超过 3 个月,部分内容可能已经过时,您可以按需阅读。如果图片无法显示或者下载链接失效,请给我反馈,谢谢!


0 0 投票数
评分

计蒜客 木桩涂涂看

$n$ 个木桩排成一排,从左到右依次编号为 $1, 2, 3…n$。每次给定 $2$ 个整数 $a, b(a \leq b)$,蒜头君便骑上他的电动车从木桩 $a$ 开始到木桩 $b$ 依次给每个木桩涂一次颜色。但是 $n$ 次以后 lele 已经忘记了第 $i$ 个木桩已经涂过几次颜色了,你能帮他算出每个木桩被涂过几次颜色吗?

输入格式
第一行是一个整数 $n(n \leq 100000)$。 接下来的 $n$ 行,每行包括两个整数 $a, b (1 \leq a \leq b \leq n)$。

3
1 1
1 2
1 3

输出格式
$n$ 个整数,第 $i$ 个数代表第 $i$ 个木桩总共被涂色的次数。

3 2 1

这题就是一个裸的差分维护。

#include <bits/stdc++.h>

using namespace std;

int n = 0;
const int MAX_N = 100007;
int dif[MAX_N] = {0};

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        dif[a]++;
        dif[b + 1]--; // 维护差分
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += dif[i];
        printf("%d%c", ans, i == n ? '\n' : ' ');
    }

    return 0;
}
0 0 投票数
评分