算法题：浇花

问题描述

HJ养了很多花（99999999999999999999999999999999999盆），并且喜欢把它们排成一排，编号0~99999999999999999999999999999999998,每天HJ都会给他的花浇水，但是他很奇怪，他会浇n(1≤n≤2∗10⁵)次水，每次都会选择一个区间[l,r]，(0≤l≤r≤10⁶),表示对区间[l,r]的花都浇一次水。现在问你，通过这些操作之后，被浇了i(1≤i≤n)次水的花的盆数。

输入格式

第一行一个n，表示HJ的操作次数，接下来的n行，表示每一次选择的浇水区间。

输出格式

输出n个数字Cnt~1~,Cnt~2~,…,Cnt~n~,（用空格隔开）Cnt~i~表示被浇了i次水的花的盆数。

样例1

输入

3
0 3
1 3
3 8

输出

6 2 1

样例2

输入

3
1 3
2 4
5 7

输出

5 2 0

对样例1解释

解决方案

思路

差分

代码

#include <iostream>

using namespace std;

int d[1000005];
int c[1000005];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int l, r;
        cin >> l >> r;

        d[l] += 1;
        d[r + 1] -= 1;
    }

    int t = 0;
    for (int i = 0; i < 1000005; ++i) {
        t += d[i];
        if (t != 0)
            c[t]++;
    }

    for (int i = 1; i <= n; ++i) {
        cout << c[i] << " ";
    }

    return 0;
}