AcWing 101. 最高的牛

题目链接：101. 最高的牛 - AcWing题库

题目中的 $M$ 对关系带给我们的信息实际上是牛之间身高的相对大小关系。

具体来说，我们建立一个数组 $C$，数组中起初全为 $0$。

若一条关系指明 $A_i$ 和 $B_i$ 可以互相看见（不妨设 $A_i < B_i$），

则把数组 $C$ 中下标为 $A_i + 1$ 到 $B_i - 1$ 的数都减去一，

意思是在 $A_i$ 和 $B_i$ 中间的牛，身高至少要比它们少 $1$。

因为第 $P$ 头牛是最高的，所以最终 $C[P]$ 一定为 0。

其他的牛和第 $P$ 头牛的身高差距就体现在数组 $C$ 中。

换言之，最后第 $i$ 头牛的身高就等于 $H + C[i]$。

如果我们朴素执行把数组 $C$ 中下标为 $A_i + 1$ 到 $B_i - 1$ 到数都减去 $1$ 的操作，

那么整个算法的时间复杂度为 $\mathcal{O}(NM)$，复杂度过高。

一个简单而高效的做法是，额外建立一个数组 $D$，

对于每对 $A_i$ 和 $B_i$，令 $D[A_i + 1]$ 减去 $1$，$D[B_i - 1]$ 加上 $1$。

其含义是：“身高减小 $1$” 的影响从 $A_i + 1$ 开始，持续到 $B_i - 1$，在 $B_i$ 结束。

最后， $C$ 就等于 $D$ 的前缀和，

即 $C[i] = \sum_{j = 1}^i {D[j]}$。

上述优化后的算法把一个区间的操作转化为左、右两个端点上的操作，再通过前缀和得到原问题的解。

这种思想很常用，我们在后面还会多次遇到。

该算法的时间复杂度为 $\mathcal{O}(N + M)$。

在本题的数据中，一条关系 $(A_i, B_i)$ 可能会输入多次，要注意检查，

对于重复的关系，只在第一次出现时执行相关操作即可。

map<pair<int, int>, bool> existed;
int c[10010], d[10010];

int main() {
    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 (existed[make_pair(a, b)]) continue;
        d[a + 1] --, d[b] ++;
        existed[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;
}

完整代码：最高的牛.cpp