poj2352Stars

二维逆序数按一个数排序转化为1维的之前用树状数组写过这次用线段树敲了下
 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 using namespace std;
 7 #define N 32010
 8 struct node
 9 {
10     int x, y;
11 }st[N];
12 int s[N<<2],f[N];
13 bool cmp(node a,node b)
14 {
15     if(a.y==b.y)
16     return a.x<b.x;
17     return a.y<b.y;
18 }
19 void build(int l,int r,int w)
20 {
21     s[w] = 0;
22     if(l==r)
23     {
24         return ;
25     }
26     int m = (l+r)>>1;
27     build(l,m,w<<1);
28     build(m+1,r,w<<1|1);
29 }
30 void pushup(int w)
31 {
32     s[w] = s[w<<1]+s[w<<1|1];
33 }
34 void update(int p,int l,int r,int w)
35 {
36     if(l==r)
37     {
38         s[w] += 1;
39         return ;
40     }
41     int m = (l+r)>>1;
42     if(p<=m)
43     update(p,l,m,w<<1);
44     else
45     update(p,m+1,r,w<<1|1);
46     pushup(w);
47 }
48 int getsum(int a,int b,int l,int r,int w)
49 {
50     if(a<=l&&b>=r)
51     {
52         return s[w];
53     }
54     int m = (l+r)>>1,res=0;
55     if(a<=m)
56     res+=getsum(a,b,l,m,w<<1);
57     if(b>m)
58     res+=getsum(a,b,m+1,r,w<<1|1);
59     return res;
60 }
61 int main()
62 {
63     int i,n;
64     while(cin>>n)
65     {
66         memset(f,0,sizeof(f));
67         build(1,n,1);
68         for(i = 1; i <= n ; i++)
69         scanf("%d%d",&st[i].x,&st[i].y);
70         sort(st+1,st+n+1,cmp);
71         for(i = 1; i <= n ; i++)
72         {
73             int s = getsum(1,st[i].x+1,1,N,1);
74             update(st[i].x+1,1,N,1);
75             f[s]++;
76         }
77         for(i = 0 ; i < n ; i++)
78         cout<<f[i]<<endl;
79     }
80     return 0;
81 }
View Code