题目链接在这里：2017-2018 ACM-ICPC, Asia Tsukuba Regional Contest
这题同时考察了线段覆盖问题的单点查询和区间查询。
区间问题第一反应想差分，之前学的都是单点查询，这里再学一个区间查询。
开一个数组up表示前面的上车的人数，一个数组down表示前面下车的人数。
然后枚举每个区间拿up[右端点]-down[左端点-1]得到区间线段个数。（这里边界是用的闭区间来举例的，本例中左闭右开的区间有所不同）
1 #include "bits/stdc++.h" 2 using namespace std; 3 const int MAX=2e5+5; 4 int n,m,a[MAX],b[MAX],up[MAX],down[MAX],now[MAX]; 5 int ans1,ans2; 6 int main(){ 7 // freopen ("i.in","r",stdin); 8 // freopen ("i.out","w",stdout); 9 int i,j,x,y; 10 scanf("%d",&n); 11 for (i=1;i<=n;i++){ 12 scanf("%d%d",&x,&y);a[i]=x,b[i]=y; 13 up[x]++; 14 down[y]++; 15 now[x]++;now[y]--; 16 m=max(m,y); 17 } 18 for (i=1;i<=m;i++){ 19 up[i]+=up[i-1]; 20 down[i]+=down[i-1]; 21 now[i]+=now[i-1]; 22 ans2=max(ans2,now[i]); 23 } 24 for (i=1;i<=n;i++) 25 ans1=max(ans1,up[b[i]-1]-down[a[i]]); 26 printf("%d %d",ans1,ans2); 27 return 0; 28 }