思路分析

（摘自这篇博客)

这道题目一个核心要点，就是如何处理这些特殊的关系，也就是两头牛互相看见。
其实题目中已经告诉我们如何处理，因为我们发现，题目中要求牛的身高最高，那么既然如此，我们完全可以将每一组关系(A,B)，看作[A+1,B−1]这组牛身高只比A,B这两头牛矮1.
因此我们可以可以利用区间处理小操作，也就是前缀和加差分。设一个数组D，D[i]为比最高牛矮多少，则D[P]=0，那么对于一组关系，我们可以这样操作,D[A+1]–,D[B]++;然后从左到右前缀和，就可以求出矮多少。

参考代码

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

const int N = 1e4 + 10;
int d[N];
map<pair<int, int>, bool> mp;	// 用于去除重复区间，存在重复区间会导致多减1

int main()
{
	int n, I, h, r;
	cin >> n >> I >> h >> r;

	while (r -- )
	{
		int a, b;
		cin >> a >> b;
		if (a > b) swap(a, b);	// 确保a小于等于b，方便之后差分
		
		if (mp[pair<int, int>(a, b)]) continue;	// 去除重复区间
		mp[pair<int, int>(a, b)] = true;
		d[a + 1] --, d[b] ++;	// 差分
	}
	
	for (int i = 1; i <= n; i ++ )
	{
		d[i] += d[i - 1];
		cout << h + d[i] << endl;	// 别忘记加上h
	}
	
	return 0;
}