[POJ 2352]Stars

danihao123 posted @ 2016年9月19日 12:17 in 题解 with tags POJ 树状数组 , 173 阅读
转载请注明出处:http://danihao123.is-programmer.com/

刚开始竟然还以为是强制离散化的二维Fenwick树……噫……注意读题。

这个题的坐标是按Y升序给出(Y相同则按X升序),所以说直接Fenwick树搞搞即可……

代码:

#include <cstdio>
const int maxn=15005,maxX=32010;
int C[maxX];
inline int lowbit(int x){
	return x&(-x);
}
inline void Add(int pos,int v){
	while(pos<=maxX){
		C[pos]+=v;
		pos+=lowbit(pos);
	}
}
inline int Sum(int x){
	register int res=0;
	while(x>0){
		res+=C[x];
		x-=lowbit(x);
	}
	return res;
}

int cnt[maxn];
int main(){
	register int i;
	int n,x,y;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d%d",&x,&y);
		x++;
		cnt[Sum(x)]++;
		Add(x,1);
	}
	for(i=0;i<n;i++){
		printf("%d\n",cnt[i]);
	}
	return 0;
}

登录 *


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