Tallest Cow（基础差分思想）_综合

原题题面：Tallest Cow

题目大意：

有 $N$ 头牛站成一排。两头牛能看见彼此，当且仅当它们中间的所有牛都比它们矮。现已知最高的牛是第 $P$ 头，且它的身高为 $H$ ，不知其他剩下 $N-1$ 头牛的身高。题目还给出了 $M$ 对关系，每队关系都有两头牛 $A$ 和 $B$ 能互相看见。求每头牛的身高最大可能是多少。

思路：

如果两头牛之间看得见，那么 $Ai+1$ 到 $Bi-1$ 之间的牛比 $Ai$ 和 $Bi$ 都小1，也就是让这个区间内的牛身高都减1，可以简单想到用一个数组来存每个下标被减了多少次。但是这个朴素算法的时间复杂度约为 $O(N*M)$ 。
所以，我们可以多建立一个数组来模拟差分的操作。如果知道 $Ai$ 和 $Bi$ 这两头牛看得见，我们就把 $D[Ai+1] - 1$ ， $D[Bi]+1$ 。其中含义是：“身高减一”的影响从 $Ai+1$ 开始，到 $Bi-1$ 结束。最后，该数组的前缀和集合就是我们存的每个下标被减了多少次的集合。

代码如下：

#include <bits/stdc++.h>
#define sc scanf
#define pf printf
#define LL long long 
using namespace std;
typedef pair<int, int> PII;
const int N = 1e4 + 10;
map<PII, bool> mp;
int c[N], d[N];
int n, m, h, p;
int main()
{sc("%d %d %d %d", &n, &p, &h, &m);for(int i = 0; i < n; i++) {int a, b;sc("%d %d", &a, &b);if(a > b) swap(a, b);if(mp[{a, b}])    continue;mp[{a, b}] = true;d[a + 1] --, d[b] ++;}for(int i = 1; i <= n; i++) {c[i] = c[i - 1] + d[i];pf("%d\n", h + c[i]);}return 0;
}