HDU-1541 Stars 树状数组-白红宇

HDU-1541 Stars 树状数组

阅读量：5872 次

发布时间：2019-06-19

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

题义为给定N个点按照先x轴，后y轴坐标排序，求某一点的左下角的星星数量，刚开始用二维的树状数组来做，结果肯定是内存不过用。

该题正解为在给定的坐标点的排序后，只对x轴坐标建立一个一维数组，对于当前状态按x轴将平面划分成M个区域，由于给定的点的y轴坐标一定是当前最高的，所以直接对横坐标前求和即可。

代码如下：

#include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
          #define MAXN 32005 using namespace std; int N, res[MAXN+5], c[MAXN+5]; inline int lowbit(int x) {
   return x & -x; } inline void modify(int pos, int val) {
   for (int i = pos; i <= MAXN; i += lowbit(i))         c[i] += val; } inline int getsum(int pos) {
   int s = 0; for (int i = pos; i > 0; i -= lowbit(i))     {
           s += c[i];        } return s; } int main() { int x, y; while (scanf("%d", &N) == 1)     {
           memset(c, 0, sizeof (c));         memset(res, 0, sizeof (res)); for (int i = 0; i < N; ++i)         {
               scanf("%d %d", &x, &y);             x++;                   res[getsum(x)]++;             modify(x, 1);         } for (int i = 0; i < N; ++i)             printf("%d\n", res[i]);     } return 0; }

转载地址：http://yuhnx.baihongyu.com/

你可能感兴趣的文章