最高的牛Tallest Cow（前缀和）- POJ 3263

Description

FJ's N (1 ≤ N ≤ 10,000) cows conveniently indexed 1..N are standing in a line. Each cow has a positive integer height (which is a bit of secret). You are told only the height H (1 ≤ H ≤ 1,000,000) of the tallest cow along with the index I of that cow.

FJ has made a list of R (0 ≤ R ≤ 10,000) lines of the form "cow 17 sees cow 34". This means that cow 34 is at least as tall as cow 17, and that every cow between 17 and 34 has a height that is strictly smaller than that of cow 17.

For each cow from 1..N, determine its maximum possible height, such that all of the information given is still correct. It is guaranteed that it is possible to satisfy all the constraints.

Input

Line 1: Four space-separated integers: N, I, H and R

Lines 2..R+1: Two distinct space-separated integers A and B (1 ≤ A, B ≤ N), indicating that cow A can see cow B.

Output

Lines 1..N: Line i contains the maximum possible height of cow i.

Sample Input

9 3 5 5

1 3

5 3

4 3

3 7

9 8

Sample Output

5

4

5

3

4

4

5

5

5

概译：N头牛排成一排，只知道最高的牛的下标I和它的高度H，然后给出R行，每行的A、B表示A可以看到B。而A可以看到B的定义为：B至少和A等高且A到B之间的牛全都严格比A矮。输出各个牛最大可能身高。

因为数据一定合法所以可以朴素地先都假设等于最高，然后每次输入A和B都把A+1~B-1之间的牛的高度都减一。但复杂度O（NR）较大，可以用前缀和的思想优化，即：把对一个区间的操作转化为左右两个端点上的操作。此题可以开一个额外的数组d，每输入A、B后，在d上的A+1下标处“--”意味着从此处开始要变矮，B下标处“++”意味着在此处结束，而d数组直接负责的是c数组，c数组代表的是第i头牛和第I头牛的身高差距，即c[I]一定等于0。

详见代码：G++

#include<iostream>
#include<cstdio>
#include<map>
#include<utility>
using namespace std;

const int maxn = 10005;
int n, I, h, r;
int c[maxn], d[maxn];
map<pair<int, int>, bool>existed;

int main()
{
    cin >> n >> I >> h >> r;
    for (int i = 0; i < r; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        if (a > b)  swap(a, b);
        if (existed[make_pair(a, b)])   continue;
        //map判断一下是否曾经操作过了
        d[a + 1]--, d[b]++;
        existed[make_pair(a, b)] = true;
    }

    for (int i = 1; i <= n; i++)
    {
        c[i] = c[i - 1] + d[i];
        printf("%d\n", h + c[i]);
    }
    return 0;
}