CodeForces 1000C Covered Points Count
程序员文章站
2022-03-24 10:49:54
...
题目:点击打开链接
题意:n个线段,问被这n个线段覆盖k次(k∈[1..n])的点的个数。
题意:n个线段,问被这n个线段覆盖k次(k∈[1..n])的点的个数。
分析:
把每个线段的起点终点分别存起来,起点标记为1,终点标记为-1,然后按照起点终点的位置排序。说不清,放个图吧。
比如
3
0 3
1 3
3 8
这组样例,排完序之后的顺序就是图中绿色的编号。
我们发现,1点的标记是1,二点的标记也是1,证明他们都是起点,一开始我们设一个计数变量,我们发现点被覆盖的次数就是计数变量原来的值加上当前点的标记,这就是为什么要给起点终点标记为1,-1了。然后到达一个起点或终点的时候,只需要后边的点的编号减去前边的点编号就是我们要的被覆盖的点的个数了。
但是有个地方就变得很难处理了,我们发现345这三个点重合了,按照原来的方式求的就不对了。怎么办呢。
只要把终点往后移一个就ok了。 可以把整个过程想象成为一个上坡、下坡过程。
代码:
#pragma comment(linker, "/STACK:102400000,102400000")///手动扩栈
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cstdio>
#include<bitset>
#include<vector>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<set>
#include<map>
using namespace std;
#define debug test
#define mst(ss,b) memset((ss),(b),sizeof(ss))
#define ll long long
#define ull unsigned long long
#define pb push_back
///#define mp make_pair
#define inf 0x3f3f3f3f
#define eps 1e-10
#define MOD 1000000007
#define PI acos(-1.0)
const int N = 1e6+10;
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
int to[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
struct nd{
ll x,f;
}p[N];
bool cmp(nd a,nd b) {
return a.x<b.x;
}
ll s[N],n;
int main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++) {
cin>>p[i].x>>p[n+i].x;
p[n+i].x++;
p[i].f=1,p[n+i].f=-1;
}
sort(p+1,p+2*n+1,cmp);
ll cnt=0;
for(int i=1;i<2*n;i++) {
cnt+=p[i].f;
s[cnt]+=(p[i+1].x-p[i].x);
}
for(int i=1;i<=n;i++)
cout<<s[i]<<" ";
cout<<endl;
return 0;
}