• 周五. 12月 9th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

暑假集训Day23 I (差分)

admin

11月 28, 2021

题目链接在这里: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 }
未来是什么样,未来会发生什么,谁也不知道。
但是我知道,
起码从今天开始努力,
肯定比从明天开始努力,
要快一天实现梦想。
千里之行,始于足下! ——《那年那兔那些事儿》

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注