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

概述https://codeforces.com/problemset/problem/1000/C                   题意： 有n个线段，覆盖[li,ri]，最后依次输出覆盖层数为1~n的点的个数。 思路： 区间线段覆盖问题，第一反应树状数组、线段树，看了看数据规模，开不了这么大的空间。 只能用差分了    代码如下： 1 #include <stdio.h> 2 #incl

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<<"---------------------"<<endl17 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 }

总结

以上是内存溢出为你收集整理的CodeForces 1000C Covered Points Count（区间线段覆盖问题，差分）全部内容，希望文章能够帮你解决CodeForces 1000C Covered Points Count（区间线段覆盖问题，差分）所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。