CodeForces 1000C Covered Points Count（区间线段覆盖问题，差

发布时间：2020-12-16 09:12:49 所属栏目：百科来源：网络整理

导读：https://codeforces.com/problemset/problem/1000/C ? ? ? ? ? ? ? ? ? 题意：有n个线段，覆盖[l i ,r i ]，最后依次输出覆盖层数为1~n的点的个数。思路：区间线段覆盖问题，第一反应树状数组、线段树，看了看数据规模，开不了这么大的空间。只能用差分

https://codeforces.com/problemset/problem/1000/C

题意：

有n个线段，覆盖[l_i,r_i]，最后依次输出覆盖层数为1~n的点的个数。

思路：

区间线段覆盖问题，第一反应树状数组、线段树，看了看数据规模，开不了这么大的空间。

只能用差分了

?代码如下：

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <string>
 5 #include <math.h>
 6 #include <algorithm>
 7 #include <vector>
 8 #include <stack>
 9 #include <queue>
10 #include <set>
11 #include <map>
12 #include <math.h>
13 const int INF=0x3f3f3f3f;
14 typedef long long LL;
15 const int mod=1e9+7;
16 #define Bug cout<<"---------------------"<<endl
17 const int maxn=2*1e5+10;
18 using namespace std;
19 
20 pair<LL,int> p[2*maxn];//注意要开两倍空间 
21 LL ans[maxn];
22 
23 int main()
24 {
25     int n;
26     scanf("%d",&n);
27     int cnt = 0;
28     for(int i = 0;i < n;i++)
29     {
30         LL l,r;//注意是long long 
31         scanf("%lld %lld",&l,&r);
32         p[i*2] = make_pair(l,1);
33         p[i*2+1] = make_pair(r+1,-1);
34     }
35     sort(p,p+n*2);
36     LL now = 0;//当前点的覆盖层数 
37     for(int i = 0;i < n*2;i++)
38     {
39         now += p[i].second;
40         if(p[i].first == p[i+1].first)    continue;//叠加差分 
41         ans[now] += p[i+1].first - p[i].first; 
42     }
43     for(int i=1;i<=n;i++)
44         printf("%lld ",ans[i]);
45     return 0;
46 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!