【差分】Acwing101 最高的牛

【差分】Acwing101 最高的牛

不存在这种交叉的关系，即A可以看见B，同时C又可以看见D，同时还交叉，如果这样的话，就可以推出来CB，是矛盾的。
所以题中可以看到的关系，都是这种嵌套形的。因为题中说了当且仅当两头牛中间的牛身高都比它们矮时，两头牛方可看到对方。
当然，也有可能一头牛可以往两边同时望。

为了求最大可能的值，最大的情况就是，比最高的牛低的牛，我们就让他的身高-1。

图片来源：https://www.acwing.com/solution/content/26418/

对差分数组本身意义的考察：差分数组中每个数表示：相邻两数之间的高度差，这个应用方向考察不多，相对陌生所以，难！

#include
#include
#include

using namespace std;

const int N = 10010;

int d[N]; // 从1-n的牛的差分数组

int main()
{
    int n, p, h, m;
    // 判重，题中说了给出的关系对可能存在重复
    set> existed;
    cin >> n >> p >> h >> m;
    d[1] = h;
    for (int i=0, a, b; i> a >> b;
        if(a>b) swap(a, b);
        if(!existed.count({a, b}))
        {
            existed.insert({a, b});
            d[a+1]--, d[b]++; //a+1到b-1都减1
        }
    }
    
    for (int i = 1; i <= n; i ++ )
    {
        d[i] += d[i - 1];
        cout << d[i] << endl;
    }
    return 0;
}