【每日一题】3月5日Tallest Cow

题意

蓝书上的原题，有一排牛一共有头，告诉你最高的那头牛是第头，且他的高度是,不知道其他头的高度，但是我们知道n对关系，即每队关系都指明了某两头牛可以相互看见，求每一头牛的最高的高度

首先我们知道，如果两头牛能够相互看见，在同一排上，那么它们之间的牛都比他们矮，因为要尽可能高，所以我们就设中间的牛比两边的牛矮1，所以我们首先把所有的牛都设为h，但是如果我们用普通的暴力很明显每一次操作都要讲之间的所有都减一，直接去暴力是不行的，所以我们这里用到差分这个做法，即记录差值，比如第三头牛比第二头牛矮1 然后后面的牛都和他一样高 因此我们只要记录第三头牛矮一 后面的直接带过去就好了

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;

const int N = 1e5 + 7;
const int INF = 0x3f3f3f3f;

map<pair<int , int> , bool> mp;
int c[N] , d[N];

int main(void){
    int n , p ,h , m;
    cin>>n>>p>>h>>m;
    for(int i = 1 ; i <= m ; ++i){
        int a , b;
        scanf("%d%d" , &a , &b);
        if(a > b)   swap(a , b);
        if(mp[make_pair(a , b)] == true)    continue;
        d[a + 1]-- , d[b]++;
        mp[make_pair(a , b)] = true; 
    }
    for(int i = 1 ; i <= n ; ++i){
        c[i] = c[i - 1] + d[i];
        printf("%d\n" , h + c[i]);
    }
    cout<<endl;
    return 0;
}