最高的牛

问题

有N头牛站成一行，被编队为1、2、3…N，每头牛的身高都为整数。当且仅当两头牛中间的牛身高都比它们矮时，两头牛方可看到对方。现在，我们只知道其中最高的牛是第P头，它的身高是H，剩余牛的身高未知。

但是，我们还知道这群牛之中存在着M对关系，每对关系都指明了某两头牛A和B可以相互看见。求每头牛的身高的最大可能值是多少。

输入格式

第一行输入整数N,P,H,M，数据用空格隔开。
接下来M行，每行输出两个整数 A 和 B ，代表牛 A 和牛 B 可以相互看见，数据用空格隔开。

输出格式

一共输出 N 行数据，每行输出一个整数。
第 i 行输出的整数代表第 i 头牛可能的最大身高。

输入样例

9 3 5 5
1 3
5 3
4 3
3 7
9 8

输出样例

5
4
5
3
4
4
5
5
5

思路

首先简单的分析可得，输入的区间之间不会出现交叉的情况。若(a,b)与(c,d)区间交叉重合部分为(e,b)，由题意可得，在(a,b)中有e小于b，在(c,d)中有e大于b，故矛盾。

只要插入新区间，就将该开区间内所有元素减1。于是将区间操作问题，利用差分序列，转化为单点操作问题。题目要求，每个位置的牛的最高身高，故初始化d[1] = h;

看图更直观的理解

代码

知识积累

swap一句解决大小顺序问题: if (a > b) swap(a, b);
利用set进行区间判重: if (!existed.count({a, b}))

差分序列求前缀和

d[1] = h; //差分序列,第一个元素为h,d[0]=0
for (int i = 1; i <= n; i++)
{
    d[i] += d[i - 1];
    cout << d[i] << endl; //差分数组的前缀和
}

#include <iostream>
#include <set>
using namespace std;

int d[10010]; //下标从1开始
set<pair<int, int>> existed;

int main()
{
    int n, p, h, m;
    cin >> n >> p >> h >> m;

    while (m--)
    {
        int a, b;
        cin >> a >> b;

        if (a > b) swap(a, b); //swap一句解决大小顺序问题
        if (!existed.count({a, b})) //利用set进行判重
        {
            existed.insert({a, b}); //新的区间插入到set中
            d[a + 1]--; //只要插入新区间，就将开区间内所有元素减1
            d[b]++;
        }
    }
    d[1] = h; //差分序列,第一个元素为h,d[0]=0
    for (int i = 1; i <= n; i++)
    {
        d[i] += d[i - 1];
        cout << d[i] << endl; //差分数组的前缀和
    }
}