线段树，求被多少个区间覆盖
[cpp]
#include
#include
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
scanf("%d%d",&x,&y);
insert(x,y,1);
}
for(i=1;i
printf("%d ",find(i,1));
}
printf("%d\n",find(n,1));
}
}
#include
#include
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
scanf("%d%d",&x,&y);
insert(x,y,1);
}
for(i=1;i
printf("%d ",find(i,1));
}
printf("%d\n",find(n,1));
}
}
以前看过一个大神的处理时间区间的代码hdu 4509的代码，用+1标记起点-1标记终点；
觉得这题也类似；
第i个点被区间覆盖的次数=在i之前的起点数+i的起点数
[cpp]
#include
#include
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
scanf("%d%d",&x,&y);
a[x][0]++;//标记多少个起点
a[y][1]++;//标记多少个起点
}
sum=0;//多少个区间
for(i=1;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;
}
#include
#include
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
scanf("%d%d",&x,&y);
a[x][0]++;//标记多少个起点
a[y][1]++;//标记多少个起点
}
sum=0;//多少个区间
for(i=1;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;
}