线段树的应用
挺简单的，不多说了。
#include<iostream> using namespace std; #define maxn 15005 struct node { int l,r,cover; }; node st[maxn*4]; int p[maxn]; int result[maxn]; int index[maxn]; void maketree(int l,int r,int i) { st[i].l=l,st[i].r=r,st[i].cover=0; int mid=(l+r)/2; if(r>l) { maketree(l,mid,i*2); maketree(mid+1,r,i*2+1); } return ; } void insert(int x,int i) { if(st[i].l==st[i].r) { st[i].cover++; return ; } else { int mid=(st[i].l+st[i].r)/2; if(x>mid) insert(x,2*i+1); else insert(x,2*i); } st[i].cover=st[2*i].cover+st[2*i+1].cover; return; } int query(int x,int i) { if(st[i].l==st[i].r) return st[i].cover; int mid=(st[i].l+st[i].r)/2; if(x>mid) return st[2*i].cover+query(x,2*i+1); else return query(x,2*i); } int cmp(const void *a,const void *b) { return *(int *)a-*(int *)b; } int getindex(int *sou,int n,int key) { int left=0,right=n-1,mid; while(left<=right) { mid=(left+right)/2; if(sou[mid]==key) return mid; else if(sou[mid]>key) right=mid-1; else left=mid+1; } } int main() { int n,x,y,i,cnt=0,t; scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d%d",&x,&y); p[i]=x,index[i]=x; } qsort(index,n,sizeof(index[0]),cmp); for(i=1;i<n;i++) if(index[i]!=index[i-1]) index[cnt++]=index[i-1]; index[cnt++]=index[n-1]; maketree(0,cnt-1,1); memset(result,0,sizeof(result)); for(i=0;i<n;i++) { t=getindex(index,cnt,p[i]); insert(t,1); result[query(t,1)-1]++; } for(i=0;i<n;i++) printf("%d/n",result[i]); return 0; }
另一种方法：树状数组，编程复杂度低，效率高
#include<iostream> using namespace std; #define N 32005 int c[N],result[N]; int low(int k) { return k&(-k); } void update(int k) { while(k<=N) { c[k]++; k+=low(k); } } int query(int k) { int sum=0; while(k>0) { sum+=c[k]; k-=low(k); } return sum; } int main() { int n,i,x,y; memset(c,0,sizeof(c)); memset(result,0,sizeof(result)); scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d%d",&x,&y); x++; update(x); result[query(x)-1]++; } for(i=0;i<n;i++) printf("%d/n",result[i]); return 0; }
