線段樹，求被多少個區間覆蓋
[cpp]
#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));
}
}
#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的起點數
[cpp]
#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;
}
#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;
}
