posts - 64, comments - 4, trackbacks - 0, articles - 0

poj2352stars 点线段树和树状数组

Posted on 2010-10-29 14:12 acronix 阅读(335) 评论(0)  编辑 收藏 引用 所属分类: hzshuai解题报告

题意:给星星的坐标,定义每个星星左下角(包括正左边和正上方)的星星数是它的level,统计各个level的星星数。

分析:乍看是个二维的统计,因为数据给出的是 y坐标升序,y相等 x坐标升序,所以可以一次读入数据,只要统计 x左边的星星数就行了,

       这道题很好的启示就是二维降一维的方法————按某种规则排序。

下面给出了线段树和树状数组的写法。

点线段树cpp代码如下:


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

const int root = 0
;
struct
 Node{
       
int
 l,r,cnt;
       
int
 lnd,rnd;
}node[
60005
];
int
 cnt,cntx;
int indx[15010
];
int x[15010],y[15010
];


void Creat(int p,int l,int
 r)
{
     node[p].l 
= l; node[p].r =
 r;
     node[p].cnt 
= 0
;
     
if (l <
 r)
     {
           
int mid = (l + r) >> 1
;
           node[p].lnd 
= ++
cnt;
           Creat(cnt,l,mid);
           node[p].rnd 
= ++
cnt;
           Creat(cnt,mid
+1
,r);
     }
     
else {node[p].lnd = node[p].rnd = -1
;}
}

void upData(int
 p)
{
     
if (node[p].l <
 node[p].r)
        node[p].cnt 
= node[node[p].lnd].cnt +
 node[node[p].rnd].cnt;
}

void Insert(int p,int
 id)
{
     
if (id == node[p].l && id ==
 node[p].r)
         node[p].cnt
++
;
     
else
 {
            
int mid = (node[p].l + node[p].r) >> 1
;
            
if (mid <
 id)
               Insert(node[p].rnd,id);
            
else
 Insert(node[p].lnd,id);
          }
     upData(p);
}

int  query(int p,int l,int
 r)
{
     
int ans = 0
;
     
if (l <= node[p].l && node[p].r <=
 r)
        ans 
=
 node[p].cnt;
     
else
{
          
int mid = (node[p].l + node[p].r) >> 1
;
          
if (mid >=
 l)
             ans 
+=
 query(node[p].lnd,l,r);
          
if (mid <
 r)
             ans 
+=
 query(node[p].rnd,l,r);
         }
     
return
 ans;
}
int Bi_Search(int
 key)
{
    
int l = 1,r = cntx+1
,mid;
    
while (l <
 r)
    {
          mid 
= (l + r) >> 1
;
          
if (indx[mid] ==
 key)
             
return
 mid;
          
else if (indx[mid] <
 key)
                  l 
= mid + 1
;
              
else r =
 mid;
    }
}

void
 Init_Index()
{
     sort(indx
+1,indx+1+
cntx);
   
//
  for (int i = 1; i <= cntx; i++)
  
//       printf("%d,",indx[i]);

     int m = 1
     
for (int i = 2; i <= cntx; i++
)
     {
         
         
if (indx[i] != indx[i-1
])
         {
            m
++
;
            indx[m] 
=
 indx[i];
         }
     }
         
     cntx 
=
 m;
}

int
 main()
{
    
int
 n,i,j,k,id;
    
int count[15010
];
    
while (scanf("%d",&n) !=
 EOF)
    {
          
for (i = 1; i <= n; i++
)
          {
              count[i] 
= 0
;
              scanf(
"%d %d",&x[i],&
y[i]);
              indx[i] 
=
 x[i];
          }
         
//
 for (i = 1; i <= n ;i++)
        
//
      printf("%d ",indx[i]);
        
//  printf("\n");

          cntx = n; 
          Init_Index();
       
/*
   for (i = 1; i <= cntx; i++)
              printf("%d ",indx[i]);
           printf("cntx = %d\n",cntx);
*/

          cnt 
= 0;
          Creat(root,
1
,cntx);
          
for (i = 1; i <= n; i++
)
          {
              id 
=
 Bi_Search(x[i]);
            
//  printf("id = %d\n",id);

              k = query(root,1,id);
            
//  printf("i = %d,k = %d\n",i,k);

              count[k] ++;
              Insert(root,id);
          }
          
for (i = 0; i < n; i++
)
              printf(
"%d\n"
,count[i]);
          
    }
    
return 0
;
}



树状数组的cpp代码:

#include<stdio.h>
int a[32002];
int level[15000
];
int
 N;
int lowbit(int
 n){
    
return n&(-
n);
}
int Sum(int
 n)
{
    
int result = 0
;
    
while(n!=0
){
        result
+=
a[n];
        n
-=
lowbit(n);
    }
    
return
 result;
}
void Update(int
 n)
{
    
while(n<=32001
){
        a[n]
++
;
        n
+=
lowbit(n);
    }
}
void
 init()
{
    
int
 i;
    
for(i=0;i<=N;i++
)
        level[i]
=a[i]=0
;
}
int
 main()
{
    
int
 x,y,i;
    scanf(
"%d",&
N);
    i
=
N;
    init();
    
while(i--
){
        scanf(
"%d %d",&x,&
y);
        level[Sum(x
+1)]++
;
        Update(x
+1
);
        
    }

    
for(i=0;i<N;i++
)
        printf(
"%d\n"
,level[i]);
}

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理