题目描述

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

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

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

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

求每头牛的身高的最大可能值是多少。

输入格式
第一行输入整数 N,P,H,M，数据用空格隔开。

接下来 M 行，每行输出两个整数 A 和 B ，代表牛 A 和牛 B 可以相互看见，数据用空格隔开。

输出格式
一共输出 N 行数据，每行输出一个整数。

第 i 行输出的整数代表第 i 头牛可能的最大身高。

数据范围
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
注意：
此题中给出的关系对可能存在重复

算法: 差分

教材里面没有提到的地方: 任意两个区间的关系是其中一个包含另一个, 或者不想交.
绝对不可能出现两个区间交叉. 自己可以画图验证一下, 会发现出现矛盾.

注意防范出现重复的数据, (A, B)与(B, A)也算是重复数据.
保存数据的时候, 记得要先对A, B进行排序.

最后, 发现P变量是冗余变量, 并不会被直接使用上, 不过, 可以用于验证程序正确性. 如果P位置上的高度不是H, 那么程序一定是有bug的, 如果P位置上的高度是H, 不能完全保证程序正确.

时间复杂度

M对关系, 每对关系的时间复杂度是O(1), M对关系就是O(M)
最后求前缀和, 时间复杂度是O(N)
因此, 总共的时间复杂度是O(M + N)

参考文献

<算法竞赛进阶指南>

Python 代码

N, P, H, M = map(int, input().split())
L = [0] * N
vis = set()

for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    if A > B:
        A, B = B, A
    if (A, B) in vis:
        continue
    vis.add((A, B))
    L[A + 1] -= 1
    L[B] += 1
for i in range(1, len(L)):
    L[i] += L[i - 1]
for e in L:
    print(e + H)