POJ 2352(Stars)树状数组

spoiler posted @ 2011年4月11日 16:33 in 树状数组经典题目 , 1335 阅读

题目分析:就是让您求位于没颗星星左下方的包括自己正下方的星星个数。因为他已经按Y轴排好序的输入了,所以只需要按着顺序在X轴上建立树状数组就可以了。

#include<iostream>
#include<stdio.h>
#define lowbit(x)  (x&(-x))
using namespace std;

const int N=32100;

int c[32100],level[15010];

int getsum(int x){
	int sum=0;
	while(x>0){
		sum+=c[x];
		x-=lowbit(x);
	}
	return sum;
}

int modify(int pos,int num){
	while(pos<=N){
		c[pos]+=num;
		pos+=lowbit(pos);
	}
	return 0;
}

int main(){
	int m, i,x,y,t;
	while(scanf("%d",&t)!=EOF){
		m=t;
		for(i=0;i<=N;i++){
			c[i]=0;
		}
		for(i=0;i<=15000;i++)
			level[i]=0;
		while(m--){
			scanf("%d %d",&x,&y);
			level[getsum(x+1)]++;
                           //用这个表记录leve出现的次数
			 modify(x+1,1);
		}
		 for(i=0;i<t;i++)
			 cout<<level[i]<<endl;
	}
	return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter