暑假集訓Day23 I (差分)

題目連結在這裡：2017-2018 ACM-ICPC, Asia Tsukuba Regional Contest

這題同時考察了線段覆寫問題的單點查詢和區間查詢。

區間問題第一反應想差分，之前學的都是單點查詢，這裡再學一個區間查詢。

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