这个题与poj的思路有点类似 点击打开poj Stars

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int MAXN = 1010;
int c[MAXN][MAXN];struct Node
{int x, y, z;
}stars[15010];int cmp(Node a, Node b)
{if(a.z != b.z)return a.z < b.z;else if(a.y != b.y)return a.y < b.y;return a.x < b.x;
}int lowbit( int x )
{return x&(-x);
}void UFset(int x, int y, int data)
{for(int i = x; i < MAXN; i += lowbit(i))for(int j = y; j < MAXN; j += lowbit(j))c[i][j] += data;
}int GetSum(int x, int y)
{int sum = 0;for(int i = x; i > 0; i -= lowbit(i))for(int j = y; j > 0; j -= lowbit(j))sum += c[i][j];return sum;
}int main()
{int N;int i, x, y, z;int s[15010];while(scanf("%d", &N) != EOF){memset(stars, 0, sizeof(stars));memset(c, 0, sizeof(c));memset(s, 0, sizeof(s));for(i = 0; i < N; ++i){scanf("%d %d %d", &x, &y, &z);stars[i].x = x, stars[i].y = y, stars[i].z = z;}sort(stars, stars+N, cmp);for(i = 0; i < N; ++i){int level = GetSum(stars[i].x+1, stars[i].y+1);//之所以要加1，那是因为可能有星星的坐标重复s[level]++;UFset(stars[i].x+1, stars[i].y+1, 1);}for(i = 0; i < N-1; ++i)printf("%d ", s[i]);printf("%d\n", s[i]);}return 0;
}