[luogu]P2879 [USACO07JAN]Tallest Cow S 差分+前缀和

传送门 :

因为没有给定 a , b a,b a,b之间的关系,所以我们需要判断一下

并且为了使得, 满足整个数组的条件,显然每条 关系 ,我们只可能运行一次

[ a , b ] [a,b] [a,b]内,所有的高度都比 a a a小,因此从差分的角度看, n u m [ a + 1 ] − − num[a+1]-- num[a+1]−−

又因为 b b b的高度一定大于 a a a的高度,所以 n u m [ b ] + + num[b]++ num[b]++

最后只需要统计一下前缀和输出答案即可

int sum[N],num[N];
int n,i,h,r;
map mp;

void solve()
{
	//n头牛 第i头牛的高度为h 最高的, R条信息
	cin>>n>>i>>h>>r;
	for(int i = 1; i <=r; i ++){
		int a,b;cin>>a>>b;
		//a,b间 所有奶牛都比 a笑
		//b的高度一定大于等于a的奶牛高度
		if(a > b) swap(a,b);
		if(mp[make_pair(a,b)]) continue;
		
		mp[make_pair(a,b)]  = 1;
		num[a+1] --;
		num[b]++;
	}
	
	for(int i = 1;i<=n;i++){
		sum[i] = sum[i-1]+num[i];
		cout<< h+ sum[i]<