CF1000C Covered Points Count（拆分思想，分成2种类型）

You are given nn segments on a coordinate line; each endpoint of every segment has integer coordinates. Some segments can degenerate to points. Segments can intersect with each other, be nested in each other or even coincide.

Your task is the following: for every k  in [1..n] , calculate the number of points with integer coordinates such that the number of segments that cover these points equals kk . A segment with endpoints  li and  ri covers point  x if and only if  li≤x≤ri .

输入格式

The first line of the input contains one integer n  ( 1≤n≤2⋅10^5 ) — the number of segments.

The next n  lines contain segments. The  i -th line contains a pair of integers li,ri (  0≤li≤ri≤10^18 ) — the endpoints of the i  -th segment.

输出格式

Print n space separated integers   cnt1,cnt2,…,cntn , where  cnti is equal to the number of points such that the number of segments that cover these points equals to i  .

题意翻译

题目大意：

给你n个区间，求被这些区间覆盖层数为k(k<=n) 的点的个数

输入格式：

第一行一个整数，n ，n<=2*10^5

以下n 行，每行有两个整数，即这个区间的左右端点l,r (0<=l<=r<=1018)

输出格式：

n个整数，即每个被覆盖层数对应的点的个数

输入输出样例

输入 #1

1. 3
2. 0 3
3. 1 3
4. 3 8

输出 #1

6 2 1

输入 #2

 3
 1 3
 2 4
5 7

输出 #2

5 2 0

说明/提示

The picture describing the first example:

Points with coordinates [0, 4, 5, 6, 7, 8] are covered by one segment, points  [1,2] are covered by two segments and point [3]  is covered by three segments.

The picture describing the second example:

Points [1, 4, 5, 6, 7] are covered by one segment, points [2, 3] are covered by two segments and there are no points covered by three segments.

题目分析我们找的是被覆盖的层数所对应的点数，于是我们可以想到建立一个结构体，放每个线段的起点，和标记层数，我们把开头记为层数加1，末尾记为层数减1，然后搞一个点顺序的排序，然后循环减出每个层数对应的点数。具体实现看代码。感谢观看，如果觉得满意的点个赞鼓励一下。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string.h>
#include<algorithm>
using namespace std;
struct Sort//定义一个类
{
  long long w,a;
  //w为位置,a为做的操作
}p[1000000];
bool cmp(Sort a,Sort b)
{
  return a.w<b.w;//按w的大小排序位置 
}
int i,j,k,sum=0,m;
long long ans[1000000],l,r,n,now=0;//注意开long long
int main()
{
  long long n;
  cin>>n;
  for(i=1;i<=n;i++)
  {
    long long l,r;
    cin>>l>>r;
    sum++;
    p[sum].w=l;
    p[sum].a=1;//区间起始位置为++
    sum++;
    p[sum].w=r+1;//结束位置为--
    p[sum].a=-1;
  }
  sort(p+1,p+sum+1,cmp);//排序
  l=p[1].w;//当前位置最小 
  now=p[1].a;//当前覆盖层数
  for(i=2;i<=sum;i++)
  {
    ans[now]+=p[i].w-l;//当前层数的个数为前后操作位置的差
    l=p[i].w;//位置 
    now+=p[i].a;// 
  }
  for(i=1;i<=n;i++)
cout<<ans[i]<<" ";//输出呀
  return 0;
}