poj 2532 stars解题报告

这道题是一道最基础的应用树状数组的题，只要理解了树状数组的含义很快就可能解决。

下面是我写的没优化过的代码，很好理解！

import java.util.Scanner;
public class Main {
 public static final int MAX = 32005;// 这里一定要大于等于32005，经测试32004 Runtime error
 public static int n;
 public static int[] c = new int[MAX];// 树状数组初始状态全为0
 public static int[] ans = new int[15010];
 // 获得2^k
 public static int lowbit(int i) {
  return i & -i;
 }
  //当x=0的时候会造成死循环
 public static void add(int i, int value) {
  while (i <= MAX) {
   c[i] += value;
   i += lowbit(i);
  }
 }
 public static int getSum(int i) {
  int sum = 0;
  while (i > 0) {
   sum += c[i];
   i -= lowbit(i);
  }
  return sum;
 }
 public static void main(String[] args) {
  Scanner sc = new Scanner(System.in);
  n = sc.nextInt();
  for (int i = 0; i < n; ++i) {
   int x = sc.nextInt();
   int y = sc.nextInt();
  //当x=0的时候会造成死循环
   // 为了避免死循环这里将x做加一处理，不会影响结果的
   // getSum(x+1)获得该star前面有几个星星
   ++x;
   ++ans[getSum(x)];
   add(x, 1);// 将x大于该star的star前面的星星数加一
  }
  for (int i = 0; i < n; ++i) {
   System.out.println(ans[i]);
  }
 }
}