继续线段树+树状数组练手题。
这题先对某坐标轴方向排序后，便能将二维降为一维处理了。没太大难度。
线段树：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,ml,cnt[15000]; struct star { int x,y; bool operator <(const star &p) const { if(y<p.y) return 1; if(y>p.y) return 0; if(x<p.x) return 1; return 0; } }s[15000]; struct node { bool b; int d; node *l,*r; }mem[64000],*root; inline void ins(int i) { int L=0,R=32000,m,lev=0; node *p=root; while(1) { m=L+R>>1; p->d++; if(L==R) { lev+=p->d-1; cnt[lev]++; break; } if(p->b) { p->b=0; p->l=&mem[ml++]; p->l->b=1; p->l->d=0; p->r=&mem[ml++]; p->r->b=1; p->r->d=0; } if(i<=m) { R=m; p=p->l; } else { lev+=p->l->d; L=m+1; p=p->r; } } } int main() { int i,j,k; while(~scanf("%d",&n)) { ml=0; root=&mem[ml++]; root->b=1; root->d=0; memset(cnt,0,sizeof cnt); for(i=0;i<n;i++) scanf("%d%d",&s[i].x,&s[i].y); sort(s,s+n); for(i=0;i<n;i++) ins(s[i].x); for(i=0;i<n;i++) printf("%d\n",cnt[i]); } return 0; } |
树状数组：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,c[32002],cnt[15000]; struct star { int x,y; bool operator < (const star &p) const { if(y<p.y) return 1; if(y>p.y) return 0; if(x<p.x) return 1; return 0; } }a[15000]; inline void add(int x) { int i; for(i=1;x<32002;i<<=1) { if(x&i) { c[x]++; x+=i; } } } inline int que(int x) { int i,sum=0; for(i=1;x;i<<=1) { if(x&i) { sum+=c[x]; x-=i; } } return sum; } int main() { int i,j,k; while(~scanf("%d",&n)) { memset(c,0,sizeof c); memset(cnt,0,sizeof cnt); for(i=0;i<n;i++) { scanf("%d%d",&a[i].x,&a[i].y); a[i].x++; a[i].y++; } sort(a,a+n); for(i=0;i<n;i++) { add(a[i].x); cnt[que(a[i].x)-1]++; } for(i=0;i<n;i++) printf("%d\n",cnt[i]); } return 0; } |