POJ 2352 Stars
因为输入是按y坐标升序的,对每个点统计在它左边的个数就是它的level(线段树);
Description
Input
Output
Sample Input
5 1 1 5 1 7 1 3 3 5 5
Sample Output
1 2 1 1 0
------------------------------------------------------------------
# include <stdio.h> # include <string.h> # define N 100005 int n, D; int cnt[4 * N], num[N]; void update(int i) { for ( ; i ^ 1; i >>= 1) { cnt[i >> 1] = cnt[i] + cnt[i ^ 1]; } } int query(int s, int t) { int ret; ret = 0; s += D-1, t += D+1; for ( ; s ^ t ^ 1; s >>= 1, t >>= 1) { if (~s & 0x1) ret += cnt[s+1]; if ( t & 0x1) ret += cnt[t-1]; } return ret; } void init(void) { for (D = 1; D < N+2; D <<= 1) ; scanf("%d", &n); memset(cnt, 0, sizeof(cnt)); memset(num, 0, sizeof(num)); } void solve(void) { int x, y, i; for (i = 1; i <= n; ++i) { scanf("%d%d", &x, &y); ++num[query(0, x)]; ++cnt[D + x], update(x+D); } for (i = 0; i < n; ++i) { printf("%d\n", num[i]); } } int main() { init(); solve(); return 0; }
------------------------------------------------------------------优质内容筛选与推荐>>