寒假差分算法

差分就是将数列中的每一项分别与前一项数做差，例如：
一个序列[1 7 6 5 2 4],差分后得到[1 6 -1 -1 -3 -2 -4]
差分序列第一个数和原序列第一个数相同（相当于第一个数减去0）
差分序列最后比原序列多一个数（相当于0减去最后一个数）

差分序列求前缀和可得原序列将原序列区间[L,R]中全部的元素+1，可以转化操作为差分序列L处+1，R+1处-1按照性质2得到，每次修改原序列一个区间+1,那么差分序列修改处增加的和减少的相同

题目描述

有 N 头牛站成一行，被编队为1、2、3…N，每头牛的身高都为整数。

当且仅当两头牛中间的牛身高都比它们矮时，两头牛方可看到对方。

现在，我们只知道其中最高的牛是第 P 头，它的身高是 H ，剩余牛的身高未知。

但是，我们还知道这群牛之中存在着 M 对关系，每对关系都指明了某两头牛 A 和 B 可以相互看见。

求每头牛的身高的最大可能值是多少。

输入格式
第一行输入整数N,P,H,M，数据用空格隔开。

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

输出格式
一共输出 N 行数据，每行输出一个整数。

第 ii 行输出的整数代表第 ii 头牛可能的最大身高。

数据范围
1≤N≤10000,1≤H≤1000000,1≤A,B≤10000,0≤M≤10000
样例
输入样例：
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牛互相看见,所以区间A,B之间的牛至少比A,B矮1得到f[A+1]--,f[B]++,然后从左到右算前缀和就可以求出矮多少了,具体可以看代码实现

#include 
#include 
#include 

using namespace std;

int N, P, H, M;
int f[10005];
bool num[10005][10005];//注意去重
//例如
//...
//3 5
//3 5
//...

int main()
{
    cin >> N >> P >> H >> M;
    f[1] = H;
    for (int i = 1, A, B; i <= M; i ++ )
    {
        cin >> A >> B; 
        if(A > B) swap(A, B);
        if(!num[A][B])
        {
            num[A][B] = 1;
            f[A + 1] --, f[B] ++;
        }
    }

    for (int i = 1; i <= N; i ++ )
        f[i] += f[i - 1], cout << f[i] << endl;
    return 0;
}