【树状数组】POJ 2352 Stars

忘是亡心i 2022-03-30 12:43 220阅读 0赞

/**
     *  @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 <iostream>
    #include <cstdio>
    #include <cmath>
    #include <algorithm>
    #include <cstring>
    #include <string>
    #include <stack>
    #include <queue>
    #include <map>
    #include <vector>
    
    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;
    }

附一篇经典翻译，学习 树状数组 [http://www.hawstein.com/posts/binary-indexed-trees.html][http_www.hawstein.com_posts_binary-indexed-trees.html]

[http_www.hawstein.com_posts_binary-indexed-trees.html]: http://www.hawstein.com/posts/binary-indexed-trees.html

发表评论取消回复

表情：

评论列表（有 0 条评论，220人围观）

还没有评论，来说两句吧...

相关阅读

相关 POJ 2352 Stars （树状数组）

Stars <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td> <t

向右看齐/ 2024年02月17日 21:27/ 0 赞/ 6 阅读

相关 POJ 2892-Tunnel Warfare【树状数组+二分】

题意：有几个村庄，D a表示a村庄被摧毁，R表示修复上一个村庄，Q a表示包含a的连续村庄有多少个，如果a被摧毁则输出0。 1. D x: The x\-th vill

ゞ浴缸里的玫瑰/ 2023年08月17日 17:35/ 0 赞/ 107 阅读

相关二维树状数组-POJ 2155 Matrix

文章目录树状数组例题题意分析代码小结树状数组 --------------------

梦里梦外;/ 2023年05月22日 14:25/ 0 赞/ 58 阅读

相关 POJ 2029 二维树状数组

二维树状数组模板题 AC代码 include <iostream> include <cstdio> include <cstring>

浅浅的花香味﹌/ 2022年11月20日 11:54/ 0 赞/ 232 阅读

相关 POJ 2352 stars

树状数组，给的数据已按以Y为主序，x为次序排列，因此只需要按所给顺序，统计其前面有几个x小于等于其本身，该值就是该点的阶数 include <cs

桃扇骨/ 2022年08月05日 20:27/ 0 赞/ 162 阅读

相关 POJ 2352-Stars（树状数组-星系）

Stars <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td>

落日映苍穹つ/ 2022年06月17日 03:28/ 0 赞/ 215 阅读

相关 POJ 3067-Japan（树状数组-逆序数）

Japan <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td>

朴灿烈づ我的快乐病毒、/ 2022年06月16日 03:58/ 0 赞/ 175 阅读

相关 HDU 1541 Stars（树状数组||线段树）

Astronomers often examine star maps where stars are represented by points on a plane and

爱被打了一巴掌/ 2022年06月12日 00:20/ 0 赞/ 223 阅读

相关【树状数组】POJ 2352 Stars

/ @author johnsondu @time 2015-8-22 @type

忘是亡心i/ 2022年03月30日 12:43/ 0 赞/ 221 阅读

相关 poj2352_II和III

这个题的第二个版本：同2299\_II,也是压缩到1--n范围内，找出已知序列的相对顺序，然后构建树状数组。这里也需要一个辅助的数组。代码： ![Contracted

灰太狼/ 2021年12月08日 19:53/ 0 赞/ 215 阅读