[USACO07JAN]区间统计Tallest Cow 差分

FarmerJohn 有n头牛，它们按顺序排成一列。 FarmerJohn 只知道其中最高的奶牛的序号及它的高度，其他奶牛的高度都是未知的。现在 FarmerJohn 手上有RRR条信息，每条信息上有两头奶牛的序号（a和b），其中b奶牛的高度一定大于等于a奶牛的高度，且a，b之间的所有奶牛的高度都比a小。现在FarmerJohn想让你根据这些信息求出每一头奶牛的可能的最大的高度。（数据保证有解）

输入格式：

第1行：四个以空格分隔的整数：n，i，h和R（n和R意义见题面; i 和 h 表示第 i 头牛的高度为 h ，他是最高的奶牛）

接下来R行：两个不同的整数a和b（1 ≤ a，b ≤ n）

输出格式：

一共n行，表示每头奶牛的最大可能高度.

题解：

建差分数组，区间修改l，r类似线段树懒惰标记。注意去重边

 

#include <bits/stdc++.h>
using namespace std;
int dif[10005];
map<pair<int,int>,bool> book;
int main()
{
	int h,n,r,i;
	int x,y;
	scanf("%d %d %d %d",&n,&i,&h,&r);
	while(r--){
		scanf("%d %d",&x,&y);
		if(x>y)swap(x,y);
		if(book[make_pair(x,y)])continue;
		book[make_pair(x,y)]=1;
		dif[x+1]--;
		dif[y]++;
	}
	for(i=1;i<=n;i++){
		dif[i]=dif[i-1]+dif[i];
		printf("%d\n",dif[i]+h);
	}
	return 0;
}