title: 最高的牛
date: 2023-12-14 21:29:19
tags: 差分
categories: 算法进阶指南
—>传送门
题目大意
思路
题目中的 M M M 对关系给我们的信息实际上是牛之间身高的相对大小的关系,我们初始化一个数组 a a a,全部为 0 0 0,有一对关系内,我们就可以得知在 ( l , r ) (l,r) (l,r) 内的牛要比端点矮,通过差分来映射出这个关系,我这个范围内的牛要比端点的至少低 1 1 1,最后每个牛的身高就是最高值与相对大小之和,即 h + a [ i ] h + a[i] 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;
}