HOJ 2678 Stars

题意：N个星星(x,y,z)，星星的等级等于x，y，z都小于等于它的星星数量，问每个等级有多少星星。

思路：最暴力的方法是三维树状数组。但是会超内存。所以我们对其中一维先排好序，然后用二维的做。

代码：

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 using namespace std;
 5 const int N=15555,M=1111;
 6 int c[M][M],ans[N];
 7 struct node
 8 {
 9     int x,y,z;
10 }a[N];
11 int cmp(node a,node b)
12 {
13     if(a.x!=b.x)
14         return a.x<b.x;
15     else if(a.y!=b.y)
16         return a.y<b.y;
17     return a.z<b.z;
18 }
19 int lowbit(int x){
20     return x&-x;
21 }
22 void add(int x,int y,int z)
23 {
24     for(int i=x;i<M;i+=lowbit(i))
25         for(int j=y;j<M;j+=lowbit(j))    
26             c[i][j]+=z;
27 }
28 int q(int x,int y)
29 {
30     int sum=0;
31     for(int i=x;i;i-=lowbit(i))
32         for(int j=y;j;j-=lowbit(j))
33             sum+=c[i][j];
34     return sum;
35 }
36 int main()
37 {
38     int n,i;
39     while(scanf("%d",&n)!=EOF)
40     {
41         for(i=1;i<=n;i++)
42             scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
43         memset(c,0,sizeof(c));
44         memset(ans,0,sizeof(ans));
45         sort(a+1,a+n+1,cmp);
46         for(i=1;i<=n;i++)
47         {
48             ans[q(a[i].y+1,a[i].z+1)]++;
49             add(a[i].y+1,a[i].z+1,1);
50         }
51         for(i=0;i<n;i++)
52             printf("%d%c",ans[i],i==n-1?'
':' ');
53     }
54     return 0;
55 }