#include
#include
int a[100005];
int main(){
int n,x,y,i;
while(scanf("%d",&n)!=EOF){
memset(a,0,sizeof(a));
if(n==0)break;
for(i=1;i<=n;i++){
scanf("%d%d",&x,&y);
a[x]++;a[y+1]--;
}
for(i=2;i<=n;i++)
a[i]+=a[i-1];
for(i=1;i<=n;i++){
if(i==1)
printf("%d",a[i]);
else
printf(" %d",a[i]);
}
printf("\n");
}
return 0;
}
但是毕竟是在学树状数组、所以还是用树状数组再次AC之、
#include
#include
int sum[100005];
int n;
int lowbit(int x){
return x&(-x);
}
int getsum(int x){
int s=0;
while(x>0){
s+=sum[x];
x-=lowbit(x);
}
return s;
}
void update(int x,int num){
while(x<=n){
sum[x]+=num;
x+=lowbit(x);
}
}
int main(){
int i,x,y;
while(scanf("%d",&n)!=EOF){
if(n==0)break;
memset(sum,0,sizeof(sum));
for(i=1;i<=n;i++){
scanf("%d%d",&x,&y);
update(x,1);
update(y+1,-1);
}
for(i=1;i<=n;i++){
printf("%d",getsum(i));
if(i