题目描述

有 N 头牛站成一行，被编队为1、2、3…N，每头牛的身高都为整数。

当且仅当两头牛中间的牛身高都比它们矮时，两头牛方可看到对方。

现在，我们只知道其中最高的牛是第 P 头，它的身高是 H ，剩余牛的身高未知。

但是，我们还知道这群牛之中存在着 M 对关系，每对关系都指明了某两头牛 A 和 B 可以相互看见。

求每头牛的身高的最大可能值是多少。
1≤N≤10000
1≤H≤1000000
1≤A,B≤10000
0≤M≤10000
此题中给出的关系对可能存在重复

样例

输入样例：
9 3 5 5
1 3
5 3
4 3
3 7
9 8
输出样例：
5
4
5
3
4
4
5
5
5

算法1

(前缀和) $O(n)$

因为两头牛a、b之间想要相互看到，那么a、b之间的牛都必须比a、b中的低值至少低1，所以我们假定所有的牛都是最高的，然后每次将a、b之间的牛的高度减一。
但因为n的范围较大，直接暴力容易超时，所以运用前缀和知识，我们只需要记录每个值与最大值的差值就行，然后先用d[i]表示从第i头到最后一头牛与最高值的差值，这样每次出现a、b，只需要d[a+1]-1，d[b]+1（到第b头就不变了，所以要+1），最后 跑一遍d[i]=d[i]+d[i-1]就可以得到真正的差值d[i]。
然后考虑重复的关系，用map映射出现次数，用pair整合a、b的关系，实现见代码

C++ 代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <map>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const int inf= 0x3f3f3f3f;
int n,p,h,m,a,b;
int d[10010];
pair<int,int>t;
map<pair<int,int>,int>q;
int main()
{
    scanf("%d%d%d%d",&n,&p,&h,&m);
    for(int i=0;i<m;i++){
        scanf("%d%d",&a,&b);
        if(a>b)  swap(a,b);
        t=make_pair(a,b);
        if(a!=b&&q[t]==0){
            q[t]++;
            d[b]++;
            d[a+1]--;
        }
    }
    for(int i=1;i<=n;i++){
        d[i]=d[i]+d[i-1];
        printf("%d\n",h+d[i]);
    }
    return 0;
}