摘要
Title: 101. 最高的牛
Tag: 差分
Memory Limit: 64 MB
Time Limit: 1000 ms

101. 最高的牛

题意

有 N 头牛站成一行，被编队为 1、2、3…N，每头牛的身高都为整数。
当且仅当两头牛中间的牛身高都比它们矮时，两头牛方可看到对方。
现在，我们只知道其中最高的牛是第 P 头，它的身高是 H ，剩余牛的身高未知。
但是，我们还知道这群牛之中存在着 M 对关系，每对关系都指明了某两头牛 A 和 B 可以相互看见。
求每头牛的身高的最大可能值是多少。

思路

当A,B能互相看见，说明他们中间的牛都比他矮，为了求最大可能值，贪心的想都矮1，那么就可以用差分将中间的牛的身高减一

代码

'''
Author: NEFU AB-IN
Date: 2022-02-15 14:58:04
FilePath: \ACM\Acwing\101.py
LastEditTime: 2022-02-15 15:22:29
'''
from collections import Counter

N = int(1e5 + 10)
a = [0] * N

d = Counter()

if __name__ == "__main__":
    n, p, h, m = map(int, input().split())
    a[1] = h #将所有的牛都变成h，即最高高度
    for i in range(m):
        l, r = map(int, input().split())
        if l > r:
            l, r = r, l
        if d[(l, r)] == 0: #判重
            a[l + 1] -= 1
            a[r] += 1
        d[(l, r)] = 1
    for i in range(1, n + 1):
        a[i] += a[i - 1]
        print(a[i])