acwing 101. 最高的牛差分经典

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

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

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

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

可以相互看见。

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

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

接下来M行，每行输出两个整数 A
和 B ，代表牛 A 和牛 B

可以相互看见，数据用空格隔开。
输出格式

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

第 i
行输出的整数代表第 i

头牛可能的最大身高。
数据范围

1≤N≤10000
,
1≤H≤1000000,
1≤A,B≤10000,
0≤M≤10000

输入样例：

输出样例：

注意：

此题中给出的关系对可能存在重复

强烈推荐y总讲题视频:https://www.acwing.com/video/85/

题意:

两个数字 $a [l e f], a [r i g]$ 能相互看见,则夹在 $l e f, r i g$ 中间的都比 $a [l e f], a [r i g]$ 小
给出能相互看见的关系,问每个位置的数字最大是多少?

题解:

差分,我们假设所有的房子开始时都一样高
当我们加入一对可见关系 $l e f, r i g$ 时,就把 $(l e f, r i g)$ 中间的值全部下凹一个单位长度
如上图是y总讲课的截图
直接差分维护区间长度即可

还有一点值得注意:
给出的区间是否可能重叠呢? 不可能(因为y总说了)
如下图

代码如下

#define debug
#ifdef debug
#include <time.h>
#include "/home/majiao/mb.h"
#endif

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <math.h>

#define MAXN ((int)1e5+7)
#define ll long long int
#define INF (0x7f7f7f7f)
#define fori(lef, rig) for(int i=lef; i<=rig; i++)
#define forj(lef, rig) for(int j=lef; j<=rig; j++)
#define fork(lef, rig) for(int k=lef; k<=rig; k++)
#define QAQ (0)

using namespace std;

#define show(x...) \ do { \ cout << "\033[31;1m " << #x << " -> "; \ err(x); \ } while (0)

void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }

namespace FastIO{

	char print_f[105];
	void read() {}
	void print() { putchar('\n'); }

	template <typename T, typename... T2>
		inline void read(T &x, T2 &... oth) {
			x = 0;
			char ch = getchar();
			ll f = 1;
			while (!isdigit(ch)) {
				if (ch == '-') f *= -1; 
				ch = getchar();
			}
			while (isdigit(ch)) {
				x = x * 10 + ch - 48;
				ch = getchar();
			}
			x *= f;
			read(oth...);
		}
	template <typename T, typename... T2>
		inline void print(T x, T2... oth) {
			ll p3=-1;
			if(x<0) putchar('-'), x=-x;
			do{
				print_f[++p3] = x%10 + 48;
			} while(x/=10);
			while(p3>=0) putchar(print_f[p3--]);
			putchar(' ');
			print(oth...);
		}
} // namespace FastIO
using FastIO::print;
using FastIO::read;

int n, m, Q, K, P, H, M, lef, rig;

int a[MAXN]; // 差分数组

void update(int L, int R) {
	a[L] ++, a[R+1] --;
}

int main() {
#ifdef debug
	freopen("test", "r", stdin);
	clock_t stime = clock();
#endif
	set<pair<int,int> > seta; //题目说可能会重复
	read(n, P, H, M);
	for(int i=1; i<=M; i++) {
		read(lef, rig);
		if(seta.find({lef, rig}) != seta.end()) continue ;
		seta.insert({lef, rig});

		if(lef > rig) swap(lef, rig);
		
		lef ++, rig --; //更新区间[L, R] 包含关系,所以先++, --
		if(lef > rig) continue ; //这种情况好像不会发生 ???
		update(lef, rig);
	}
	int sum = 0, ans = 0; //对于前缀和sum是正数就说明要下凹
	for(int i=1; i<=n; i++) {
		ans = H;
		sum += a[i]; //求前缀和
		if(sum > 0) ans -= sum; //下凹sum个单位长度
		printf("%d\n", ans);
	}




#ifdef debug
	clock_t etime = clock();
// printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif 
	return 0;
}