A,B可以相互看到,所以a,b之间的牛至少要比a、b的身高减1,因此设置一个差分数组使[a+1,b-1]这个区间减1,最终最高的牛的差分数组的前缀和一定是0,因为他没有被任何牛阻挡,其他的牛的身高就是最高的加上应该减去的。
#include<iostream>
#include<map>
using namespace std;
const int N=10010;
typedef pair<int,int> PII;
map<PII,bool> existed;
int n,p,h,m;
int d[N],c[N];
int main(){
cin>>n>>p>>h>>m;
while(m--){
int a,b;
cin>>a>>b;
if(a>b) swap(a,b);
if(!existed[{a,b}]){
d[a+1]-=1;
d[b]+=1;
existed[{a,b}]=true;
}
}
for(int i=1;i<=n;i++){
c[i]=c[i-1]+d[i];
printf("%d\n",h+c[i]);
}
return 0;
}