POJ 题解：Stars (树状数组应用)

题目理解

题目要求我们统计二维平面中星星的等级。一个星星的等级定义为在其左下方（包括正左和正下）的星星数量。给定$n$颗星星的坐标$(x_i, y_i)$（按$y$坐标升序给出），要求计算每个等级（0到$n-1$）的星星数量。

算法思路

关键观察

1. 输入特性：星星已按$y$坐标升序排列，因此只需考虑$x$坐标
2. 问题转化：对于每个星星$i$，其等级等于在它之前输入且$x$坐标不大于$x_i$的星星数量
3. 数据结构选择：使用**树状数组（Fenwick Tree）**高效维护和查询前缀和

树状数组操作

1. 初始化：清零树状数组
2. 查询操作：$sum(x)$计算$x$坐标不超过$x$的星星数量
3. 更新操作：$update(x)$将$x$位置的值加1

代码解析

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 32010;  // 最大坐标范围

int cnt[maxn];  // 存储每个等级出现的次数
int a[maxn];    // 树状数组

// 计算前x项的和
int sum(int x) {
    int ans = 0;
    for(int i = x; i > 0; i -= (i & -i)) {  // lowbit操作
        ans += a[i];
    }
    return ans;
}

// 更新树状数组
void update(int x) {
    for(int i = x; i <= maxn; i += (i & -i)) {  // lowbit操作
        a[i]++;
    }
}

int main() {
    int n;
    while(~scanf("%d", &n)) {
        memset(cnt, 0, sizeof(cnt));
        memset(a, 0, sizeof(a));
        
        for(int i = 0; i < n; i++) {
            int x, y;
            scanf("%d%d", &x, &y);  // y坐标其实不需要使用
            cnt[sum(x + 1)]++;      // x+1避免0下标，查询当前星星的等级
            update(x + 1);          // 将当前星星加入树状数组
        }
        
        for(int i = 0; i < n; i++) {
            printf("%d\n", cnt[i]);  // 输出每个等级的数量
        }
    }
    return 0;
}

复杂度分析

• 时间复杂度：

  • 每次查询和更新操作都是$O(\log n)$
  • 对于$n$个星星，总复杂度为$O(n \log n)$

• 空间复杂度：

  • 树状数组需要$O(max_x)$的空间，其中$max_x$是坐标最大值

关键点说明

1. 坐标偏移：

   • 使用x+1避免处理0下标（树状数组通常从1开始）

2. 输入特性利用：

   • 由于输入按$y$升序给出，只需比较$x$坐标即可确定相对位置

3. 等级统计：

   • $cnt[sum(x+1)]++$直接统计每个等级的出现次数

数学表达

1. 等级定义：

   $$\text{level}_i = \sum_{j<i} \mathbb{I}(x_j \leq x_i) $$

   其中$\mathbb{I}$是指示函数

2. 树状数组操作：

   • 查询操作：$\text{sum}(x) = \sum_{i=1}^x a[i]$
   • 更新操作：$\text{update}(x): a[x] \leftarrow a[x] + 1$

注意事项

1. 数组大小：

   • 根据题目要求，坐标最大为32000，因此数组大小设为32010

2. 输入输出：

   • 使用$scanf$和$printf$提高IO效率
   • 处理多组测试数据直到EOF

3. 初始化：

   • 每组数据开始前清空树状数组和计数数组

扩展思考

1. 如果$y$坐标无序：

   • 需要先按$y$坐标排序，再按$x$坐标处理

2. 更高维度的扩展：

   • 可以使用多维树状数组处理更高维度的类似问题

3. 替代数据结构：

   • 线段树也可以实现相同的功能，但代码量稍大

这个解法充分利用了树状数组高效处理动态前缀和的特性，是处理此类统计问题的经典方法。