计蒜客 木桩涂涂看

$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;
}