[CSP-J 2022 山东] 植树节

知识点

差分、前缀和、区间加法

解题思路

对每个闭区间[a,b]，令diff[a]加1、diff[b+1]减1。按坐标做前缀和，它就是每棵树的浇水次数，取最大值。

正确性说明

某区间在a开始贡献1，到b之后的b+1取消贡献，所以前缀和在且仅在闭区间内包含该区间的1次浇水。叠加全部区间后取最大即为答案。

易错点

坐标从0开始；b=1000000时仍需能写入b+1；不能将闭区间写成半开区间。

复杂度

时间O(n+U)，空间O(U)，U=1000001。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin>>n;vector<int>d(1000002);for(int i=0,a,b;i<n;i++){cin>>a>>b;++d[a];--d[b+1];}int cur=0,ans=0;for(int i=0;i<=1000000;i++)cur+=d[i],ans=max(ans,cur);cout<<ans<<'\n';}