HDU 1556 Color the ball（差分）

用差分实现区间操作

一维

给定一个长度为n的数列a，要求支持操作add(L,R,k)表示对a[L]~a[R]的每个数都加上k。并求修改后的序列a。

设原数组为a[i]a[i], 设数组d[i]=a[i]−a[i−1](a[0]=0)，则 a[i]=∑ij=1d[j]

更新操作update(s, t, d)把区间A[s]…A[t]都增加d，我们引入一个数组delta[i]，表示

A[i]…A[n]的共同增量，n是数组的大小。那么update操作可以转化为：

1）令delta[s] = delta[s] + d，表示将A[s]…A[n]同时增加d，但这样A[t+1]…A[n]就多加了d

2）再令delta[t+1] = delta[t+1] - d，表示将A[t+1]…A[n]同时减d

我们考虑用差分的做法。这里需要一个辅助数组c，c用来记录某一个位置上的总改变量。c[i]表示的是i~n这些元素都加上c[i]这个数。我们对[L,R]区间进行加值操作，在c[L]处加一个k，在c[R+1]处就减去一个k。最后求序列的每个位置变成了多少，只需要求一下c数组的前缀和，然后和原数组按位相加就好。

二维

一个n*m的矩阵，要求支持操作add(x1,y1,x2,y2,a)，表示对于以(x1,y1)为左下角，(x2,y2)为右上角的矩形区域，每个元素都加上a。要求修改后的矩阵。

做法和一维类似。用数组c存储总改变量。在 c[x1][y1] 处加上 a ，在 c[x2 + 1][y1] 和 c[x1][y2 + 1] 处减a，在 c[x2 + 1][y2 + 1] 再加上a。最后(i,k)位置上的数值就是c数组在(i,k)位置的前缀和。

Description

N个气球排成一排，从左到右依次编号为1,2,3….N.每次给定2个整数a b(a <= b),lele便为骑上他的“小飞鸽”牌电动车从气球a开始到气球b依次给每个气球涂一次颜色。但是N次以后lele已经忘记了第I个气球已经涂过几次颜色了，你能帮他算出每个气球被涂过几次颜色吗？

Input

每个测试实例第一行为一个整数N,(N <= 100000).接下来的N行，每行包括2个整数a b(1 <= a <= b <= N)。当N = 0，输入结束。

Output

每个测试实例输出一行，包括N个整数，第I个数代表第I个气球总共被涂色的次数。

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

Code

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int a[100005];

int main()
{
    int n;
    while(cin >> n && n)
    {
        int left, right;
        for(int i = 0; i < n; ++i)
        {
            cin >> left >> right;
            a[left] ++;
            a[right + 1] --;
        }
        for(int i = 1; i <= n; ++i)
        {
            a[i] += a[i - 1];
            printf("%d%c", a[i], i == n ? '\n' : ' ');
        }
        memset(a, 0, sizeof(a));
    }
    return 0;
}