POJ - 3263 Tallest Cow（差分，前缀和）

POJ - 3263

这道题目一个核心要点，就是如何处理这些特殊的关系，也就是两头牛互相看见。
其实题目中已经告诉我们如何处理，因为我们发现，题目中要求牛的身高最高，那么既然如此，我们完全可以将每一组关系(A,B)，看作[A+1,B?1]这组牛身高只比A,B这两头牛矮1.

因此我们可以可以利用区间处理小操作，也就是前缀和加差分。设一个数组DD，D[i]D[i]为比最高牛矮多少，则D[P]=0，那么对于一组关系，我们可以这样操作,D[A+1]–,D[B]++;然后从左到右前缀和，就可以求出矮多少。

#include<iostream>
#include<set>
using namespace std;set<pair<int,int> >cnt;
const int N = 10010;int n,p,h,m;
int d[N];int main()
{
    cin>>n>>p>>h>>m;d[1]=h;for(int i=0;i<m;i++){
    int a,b;cin>>a>>b;if(a>b) swap(a,b);if(!cnt.count({
    a,b})){
    cnt.insert({
    a,b});d[a+1]--;d[b]++;}} for(int i=1;i<=n;i++){
    d[i]+=d[i-1];cout<<d[i]<<endl; }return 0;
}