poj2352Stars

http://poj.org/problem?id=2352

二维逆序数 按一个数排序 转化为1维的 之前用树状数组写过 这次用线段树敲了下

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 using namespace std;

 #define N 32010

 struct node

 {

     int x, y;

 }st[N];

 int s[N<<],f[N];

 bool cmp(node a,node b)

 {

     if(a.y==b.y)

     return a.x<b.x;

     return a.y<b.y;

 }

 void build(int l,int r,int w)

 {

     s[w] = ;

     if(l==r)

     {

         return ;

     }

     int m = (l+r)>>;

     build(l,m,w<<);

     build(m+,r,w<<|);

 }

 void pushup(int w)

 {

     s[w] = s[w<<]+s[w<<|];

 }

 void update(int p,int l,int r,int w)

 {

     if(l==r)

     {

         s[w] += ;

         return ;

     }

     int m = (l+r)>>;

     if(p<=m)

     update(p,l,m,w<<);

     else

     update(p,m+,r,w<<|);

     pushup(w);

 }

 int getsum(int a,int b,int l,int r,int w)

 {

     if(a<=l&&b>=r)

     {

         return s[w];

     }

     int m = (l+r)>>,res=;

     if(a<=m)

     res+=getsum(a,b,l,m,w<<);

     if(b>m)

     res+=getsum(a,b,m+,r,w<<|);

     return res;

 }

 int main()

 {

     int i,n;

     while(cin>>n)

     {

         memset(f,,sizeof(f));

         build(,n,);

         for(i = ; i <= n ; i++)

         scanf("%d%d",&st[i].x,&st[i].y);

         sort(st+,st+n+,cmp);

         for(i = ; i <= n ; i++)

         {

             int s = getsum(,st[i].x+,,N,);

             update(st[i].x+,,N,);

             f[s]++;

         }

         for(i =  ; i < n ; i++)

         cout<<f[i]<<endl;

     }

     return ;

 }