最高的牛

2023-12-14 23:06:39

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;
}

文章来源:https://blog.csdn.net/m0_73865722/article/details/135005018
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。