学步园

线段树，求被多少个区间覆盖

#include<stdio.h>
#include<string.h>
struct tree
{
	int left,right,count;
}p[300100];
void build(int l,int r,int k)
{
	int mind=(l+r)/2;
	p[k].left=l;
	p[k].right=r;
	p[k].count=0;
	if(l==r)
	 return ;
	build(l,mind,k*2);
	build(mind+1,r,k*2+1);
}
void insert(int l,int r,int k)
{
	if(p[k].left==l&&p[k].right==r)
	{
		p[k].count++;return;
	}
	int mind=(p[k].left+p[k].right)/2;
	if(r<=mind)
		insert(l,r,k*2);
	else if(l>mind)
		insert(l,r,k*2+1);
	else
	{
		insert(l,mind,k*2);
		insert(mind+1,r,k*2+1);
	}
}
int find(int a,int k)
{
	int sum=p[k].count;
	if(p[k].left==p[k].right)
		return sum;
	int mind=(p[k].left+p[k].right)/2;
	if(a<=mind)
		sum+=find(a,k*2);
	else sum+=find(a,k*2+1);
	return sum;
}
int main()
{
	int i,j,n,m,x,y;
	while(scanf("%d",&n)!=-1&&n)
	{
		build(1,n,1);
		for(i=0;i<n;i++)
		{
			scanf("%d%d",&x,&y);
			insert(x,y,1);
		}
		for(i=1;i<n;i++)
		{
			printf("%d ",find(i,1));
		}
		printf("%d\n",find(n,1));

	}
}

以前看过一个大神的处理时间区间的代码hdu 4509的代码，用+1标记起点-1标记终点；

觉得这题也类似；

第i个点被区间覆盖的次数=在i之前的起点数+i的起点数

#include<stdio.h>
#include<string.h>
int a[100002][2];
int main()
{
	int i,j,n,m,x,y,sum;
	while(scanf("%d",&n)!=-1&&n)
	{
		memset(a,0,sizeof(a));
		for(i=0;i<n;i++)
		{
			scanf("%d%d",&x,&y);
			a[x][0]++;//标记多少个起点
			a[y][1]++;//标记多少个起点
		}
		sum=0;//多少个区间
		for(i=1;i<n;i++)
		{
			sum+=a[i][0];//前边的起点数加上起点在i的起点数
		   printf("%d ",sum);
		    sum-=a[i][1];//减去终点数
		}
		sum+=a[n][0];
		printf("%d\n",sum);
		sum-=a[n][1];
	}
	return 0;
}