数组：4.覆盖的点数

【问题描述】

       给定坐标轴上的 n 个区间段，每个段的端点为整数坐标。有些段可以是一个点，可以彼此相交、相互嵌套，甚至重合，对于任意区间，0≤li ≤ ri≤6×105。

       任务如下：对于每个 k ∈[1..n]，计算被 k 个区间段覆盖的整数坐标点的个数。点 x被端点为 li 和 ri  的区间段覆盖，当且仅当 li≤ x ≤ri。

【输入形式】

       输入的第一行为一个整数 n（1≤ n ≤ 2⋅ 105），区间段的个数。

       接下来的 n 行，每行一个整数对 li 和 ri，表示第 i 个区间的端点。
【输出形式】

       输出 n 个用空格分隔的整数cnt1、cnt2、...、cntn，这里 cnti 为被 i 个区间覆盖的点的个数。

【样例输入1】

3
0 3
1 3
3 8

【样例输出1】

6 2 1

【样例输入2】

3
1 3
2 4
5 7

【样例输出2】

5 2 0

【样例说明】

样例1描述如下:

坐标点0、4、5、6、7、8被1个区间段覆盖，点1、2被2个区间段覆盖， 点3倍3个区间段覆盖。

样例2描述如下:

坐标点1、4、5、6、7被1个区间段覆盖，点2、3被两个区间段覆盖，每有点被3个区间段覆盖Points 

【评分标准】

#include
using namespace std;
int main()
{
	int n,l,r;
	int arr[60];
	cin>>n;
	int arr2[n];
	for(int j=0;j<60;j++)
	{
		arr[j]=0;//对数组arr中元素进行依次归零
		arr2[j]=0;
	}
	/*-------------------
	      越界开始 
    --------------------*/ 
	for(int i=0;i
	{
		cin>>l>>r;
		for(int k=l;k<=r;k++)
		{
			arr[k]++;
		} 
	}                               //截至此步为止arr中每个元素都为重复多少次了 
	for(int m=1;m<=n;m++)
	{
		for(int p=0;p<60;p++)
		{
			if(arr[p]==m)
			arr2[m]++;
		}
	}
	/*-------------------
	      越界结束 
    --------------------*/
	for(int i=1;i<=n;i++)
	{
			cout<" ";
	}
	system("pause");
	return 0;
}

这样编运行时结果正确，但是会造成数组越界

所以可以使用指针，分别给两个数组分配堆内存：

#include
using namespace std;
int main()
{
	int n,l,r,len;
	len=600000;
	int *arr=new int[len];
	cin>>n;
	int *arr2=new int[n+1];
	for(int j=0;j
	{
		arr[j]=0;//对数组arr中元素进行依次归零
	}
	for(int j=0;j1;j++)
	{
		arr2[j]=0;
	}
	for(int i=0;i
	{
		cin>>l>>r;
		for(int k=l;k<=r;k++)
		{
			arr[k]++;
		} 
	}//截至此步为止arr中每个元素都为重复多少次了 
	for(int m=1;m<=n;m++)
	{
		for(int p=0;p
		{
			if(arr[p]==m)
			arr2[m]++;
		}
	}
	for(int i=1;i<=n;i++)
	{
			cout<" ";
	}
	delete[]arr;
	system("pause");
	return 0;
}