序列的区间操作

知识点

这是一个比较零碎的小点，之前并不知道，只会暴力233333
一个数组(a)（假设数组长为(a)），然后数组(a)的下标在([l,r])范围内元素加上/减去一个数(x)，可以这样操作：

(a[l]=a[l]+n;a[r+1]=a[r+1]-n)

求操作后的(a[k])即为：

(a[k]=sum_{i=0}^{k}a[i])

相关题目

eg1：HDU 1556 Color the ball （原题戳我~）

Sample Input

3
1 1
2 2
3 3
3
1 1
1 2
1 3
0

Sample Output

1 1 1
3 2 1

代码样例

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <set>
#include <string>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
using namespace std;
typedef long long ll;

const int maxn = 100000 + 10;
int ball[maxn];

int main()
{
    int n;
    while (cin >> n)
    {
        if (n == 0)
            break;
        memset(ball, 0, sizeof(ball));
        for (int i = 0; i < n; i++)
        {
            int a, b;
            cin >> a >> b;
            ball[a]++;
            ball[b + 1]--;
        }
        for (int i = 1; i <= n; i++)
        {
            ball[i] += ball[i - 1];
            if (i < n)
                cout << ball[i] << " ";
            else
            {
                cout << ball[i] << endl;
            }
        }
    }
    // system("pause");
    return 0;
}

完~