101. 最高的牛

这是一个比较典型使用差分技巧的题。
题目中给出了M对牛可以互相看见对关系，那么对于两个可以互相看到的牛a，b。在差分数组B中，只需要让

B[a+1] -= 1
B[b] += 1

这样做可以保证a，b之间的牛至少比a，b少一个高度，这样就能使得a，b可以互相看见
进过M次处理之后，就可以把差分数组转换成原始数组，原始数组还有加上最高位与原始数组上对应位的差值，也就是加上H-A[p]
因为此题的M对关系可能重复，这里我用的set进行去重复

#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
const int maxn = 1e6+10;
typedef pair<int,int> pii;

int N,P,H,M;
int A[maxn],B[maxn];//高度数组，差分数组
set<pii> st;
int main(){
    cin>>N>>P>>H>>M;
    int a,b;
    while(M--){
        scanf("%d%d",&a,&b);
        if(a>b) swap(a,b);
        if(a!=b) st.insert({a,b});
    }
    for(auto p:st){
        B[p.first+1]--;
        B[p.second]++;
    }
    for(int i = 1;i<=N;i++) A[i] = A[i-1]+B[i];
    for(int i = 1;i<=N;i++){
        printf("%d\n",A[i]+H-A[P]);
    }
    return 0;
}