[Acwing] AcWing 101. 最高的牛 差分

前言

总算可以水一题了 awa 传送门 : https://www.acwing.com/problem/content/103/

思路

题目要求的是 两边的牛高 中间的牛矮

因为数据范围很大 我们不可能 给他们 遍历一遍+1 -1

所以我们可以使用差分进行+1 -1

但是题目最高又限制了 最高的牛 所以我们还需要查重

差分步骤: n u m [ l ] + + num[l]++ num[l]++ n u m [ r + 1 ] + + num[r+1]++ num[r+1]++ n u m [ l + 1 ] − − num[l+1]- - num[l+1]−− n u m [ r ] − − num[r] - - num[r]−− 看不懂的 要回去巩固一下 差分 哦

CODE

#include 
using namespace std;
using ll= long long;
const int N = 1e4+10;

set s;
int num[N];

void solve()
{
    int n,p,h,m;cin>>n>>p>>h>>m;

    while(m -- )
    {
        int a,b;
        cin>>a>>b;
        if(b