最高的牛(一般问题转化为差分)

传送门：101. 最高的牛 - AcWing题库

思路：每一对给出的牛之间的牛的身高肯定都严格小于两个端点的牛，设两个端点a,b的牛的身高为0，a+1到b-1之间就是-1，最高的牛最后肯定是0，可能不止一个0，每一次都要对区间内的所有数减1，可以用差分的方法，c[a+1]-=1,c[b]+=1.最后对差分数列做一个前缀和，每头牛的身高就是h+c[i]

代码：

#include 
#include 
#include 
using namespace std;
typedef pair<int ,int> PII;
const int N=1e4+10;
int c[N];
int d[N];
int n,p,h,m;
mapint>mp;
int main()
{
    cin>>n>>p>>h>>m;
    while(m--)
    {
        int a,b;
        cin>>a>>b;
         if(a>b) swap(a,b);
        if(mp[{a,b}]) continue;
        mp[{a,b}]=1;
 
        c[a+1]-=1;
        c[b]+=1;
    }
    for(int i=1;i<=n;i++)
    c[i]+=c[i-1];
    for(int i=1;i<=n;i++)
        cout<
return 0;
}