最高的牛

title: 最高的牛
date: 2023-12-14 21:29:19
tags: 差分
categories: 算法进阶指南

—>传送门

题目大意

思路

题目中的 $M$ 对关系给我们的信息实际上是牛之间身高的相对大小的关系，我们初始化一个数组 $a$，全部为 $0$，有一对关系内，我们就可以得知在 $(l,r)$ 内的牛要比端点矮，通过差分来映射出这个关系，我这个范围内的牛要比端点的至少低 $1$，最后每个牛的身高就是最高值与相对大小之和，即 $h+a[i]$。

时间复杂度

将区间操作转化了左右端点上的操作，时间复杂度为 O(N + M)。

代码

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define sz size()
#define bpt __builtin_popcountll

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;

const int N = 6E5 + 10, mod = 1e9 + 7;


int main()
{
	int n,p,h,m;
	cin >> n >> p >> h >> m;
	vector<int>a(n + 2);
	map<PII,int> mp;
	for(int i = 0; i < m; i++){
	    int l,r;
	    cin >> l >> r;
	    if(l > r) swap(l,r);
	    if(mp[{l,r}]) continue;
	    mp[{l,r}] = 1;
	    a[l + 1] --,a[r] ++;
	}
	for(int i = 1; i <= n; i++){
	    a[i] += a[i - 1];
	}
	for(int i = 1; i <= n; i++){
	    cout << h + a[i] << endl;
	}
    return 0;
}