101. 最高的牛

#include <iostream>
#include <set>
using namespace std;

const int N = 10010;

int height[N];

int main()
{
	int n, p, h, m;
	cin >> n >> p >> h >> m;
	height[1] = h;
	
	set<pair<int, int> > existed;　　// 题目中给定的数据可能会有重复，故用set去重
	for(int i = 1, a, b; i <= m; ++ i)
	{
		cin >> a >> b;
		if(a > b)	swap(a, b);　　// 端点的大小要进行比较
		if(!existed.count({a, b}))
		{
			existed.insert({a, b});
			height[a + 1] --;　　// 差分数组的应用，区间[a + 1, b - 1]内所有的数-1
			height[b] ++;
		}
	}
	
	for(int i = 1; i <= n; ++ i)
	{
		height[i] += height[i - 1];
		cout << height[i] << endl;　　// 前缀和得到每头牛的身高
	}
	
	return 0;
}