HDU 1541 - Stars

题目描述

Stars

解法：树状数组-降维

其实，我们知道每颗星星的level其实就是对应树状部分$c[...]$数组中的一个元素值。至于降维，也就是说每一组输入中的纵坐标是无用的。每输入一组坐标，我们计算其level，然后更新树状部分。

在树状数组中，数组$a[...]$其实是没有用到的，因此我们可以使用它来存储每个 level 对应星星数。

#include <bits/stdc++.h>using namespace std;int a[32005], c[32005];
int n = 32005, k, xx, yy;int lowbit(int x){
    return x&(-x);}int sum(int x)
{
    int s = 0;for(int i=x;i;i-=lowbit(i))s += c[i];return s;
}void update(int x, int v)
{
    for(int i=x;i<=n;i+=lowbit(i))c[i] += v;
}int main()
{
    while(~scanf("%d", &k)){
    memset(a, 0, sizeof(a));memset(c, 0, sizeof(c));for(int i=0;i<k;i++){
    scanf("%d%d", &xx, &yy);xx++; // 横坐标右移一个单位，防止 xx = 0a[sum(xx)]++;update(xx, 1);}for(int i=0;i<k;i++)printf("%d\n", a[i]);}return 0;
}