P11853 [CSP-J2022 山东] 植树节

Dijkstra_zyl · 2025-09-28 21:49:55 · 题解

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e6+10;
int a[maxn],b[maxn],ans = 0,mr = 0;
signed main(){
    int n; cin >> n;
    for(int i = 1;i <= n;i++){
        int l,r; cin >> l >> r;
        l++,r++;//避免为0
        mr = max(mr,r);//更新最右区间 
        a[l]++,a[r+1]--;//先差分 
    }
    b[0] = a[0];//零也被浇了 
    for(int i = 1;i <= mr;i++) {
        b[i] += b[i-1] + a[i];//前缀和 
        ans = max(ans,b[i]);//取最大值 
    }
    cout << ans;
    return 0;
}