树状数组：
#include<iostream>
using namespace std;
struct Node{
int x,y;
}a[15001];
int N;
int c[32001];
int ans[15000];
int cmp(const void* no1,const void* no2){
Node *nox=(Node*)no1,*noy=(Node*)no2;
if(nox->x!=noy->x) return nox->x-noy->x;
else return nox->y-noy->y;
}
inline int lowbit(int x){
return x^(x&(x-1));
}
int getsum(int x){
int s=0;
while(x){
s+=c[x];
x-=lowbit(x);
}
return s;
}
void modify(int x){
while(x<=32001){
c[x]++;
x+=lowbit(x);
}
}
int main()
{
scanf("%d",&N);
for(int i=0;i<N;++i){
scanf("%d%d",&a[i].x,&a[i].y);
a[i].y++;
}
qsort(a,N,sizeof(Node),cmp);
memset(ans,0,sizeof(ans));
memset(c,0,sizeof(c));
for(int i=0;i<N;++i){
ans[getsum(a[i].y)]++;
modify(a[i].y);
}
for(int i=0;i<N;++i)
printf("%d\n",ans[i]);
return 0;
}
线段树：
#include<iostream>
using namespace std;
struct Node{
int a,b;
int cover,sum;
}tree[1500000];
int N;
int ans[15010];
void build(int Num,int la,int lb){
tree[Num].a=la;
tree[Num].b=lb;
tree[Num].cover=tree[Num].sum=0;
if(la<lb){
int mid=(la+lb)>>1;
build(Num<<1,la,mid);
build((Num<<1)+1,mid+1,lb);
}
}
void insert(int Num,int la,int lb){
if(tree[Num].a==la&&tree[Num].b==lb){
tree[Num].cover++;
tree[Num].sum++;
return;
}
int mid=(tree[Num].a+tree[Num].b)>>1;
if(lb<=mid) insert(Num<<1,la,lb);
else if(la>mid) insert((Num<<1)+1,la,lb);
tree[Num].sum=tree[Num].cover+tree[Num<<1].sum+tree[(Num<<1)+1].sum;
}
int query(int Num,int la,int lb){
if(tree[Num].a==la&&tree[Num].b==lb)
return tree[Num].sum;
int mid=(tree[Num].a+tree[Num].b)>>1;
if(lb<=mid) return query(Num<<1,la,lb);
else if(la>mid) return query((Num<<1)+1,la,lb);
else return query(Num<<1,la,mid)+query((Num<<1)+1,mid+1,lb);
}
int main()
{
scanf("%d",&N);
memset(ans,0,sizeof(ans));
build(1,1,32001);
int x,y;
for(int i=0;i<N;++i){
scanf("%d%d",&x,&y);
ans[query(1,1,x+1)]++;
insert(1,x+1,x+1);
}
for(int i=0;i<N;++i)
printf("%d\n",ans[i]);
return 0;
}
posted on 2009-05-29 23:38
xfstart07 阅读(287)
评论(0) 编辑 收藏 引用