【树状数组】POJ 2352 Stars-白红宇

【树状数组】POJ 2352 Stars

阅读量：6884 次

发布时间：2019-06-27

本文共 1061 字，大约阅读时间需要 3 分钟。

/** *  @author           johnsondu *  @time             2015-8-22 *  @type             Binary Index Tree *                      ignore the coordinate of y and  *                      process as 1D conditions. *  @url              http://poj.org/problem?id=2352 */#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               using namespace std;const int N = 15005;const int M = 32010;int level[N], c[M];int lowbit(int x) { return (x & (-x)) ;}// 向上更新void update(int x, int v) { while(x < M) { c[x] += v; x += lowbit(x); }}// 获取当前节点及下面的值的个数int getSum(int x) { int sum = 0; while(x > 0) { sum += c[x]; x -= lowbit(x); } return sum;}int main(){ int n, x, y; scanf ("%d", &n); memset(level, 0, sizeof(level)); memset(c, 0, sizeof(c)); for(int i = 1; i <= n; i ++) { scanf("%d%d", &x, &y); ++ level[getSum(x + 1)]; update(x+1, 1); } for(int i = 0; i < n; i ++) { cout << level[i] << endl; } return 0;}