POJ2352 Stars 树状数组简单应用

题目让你求星星等级，对于每个星星都会有 x,y,坐标，对于某一个星星的等级就是 所有x坐标以及y坐标都小于等于它的坐标的 星星总数，题目给n个星星，然后输出星星等级为等级0到n-1的 的数量

因为星星的y坐标输入情况是不会出现大小下降的情况，然后所有点的坐标是不会重复的，所以直接只对x坐标进行处理就可以了，那么就是利用树状数组 对于 x坐标加进去的 求和，即为 小于它的数目，再加上1也就是等级，由于坐标有可能为0，0树状数组处理的时候坐标要加1

#include<iostream>
#include<cstdio>
#include<list>
#include<algorithm>
#include<cstring>
#include<string>
#include<stack>
#include<map>
#include<vector>
#include<cmath>
#include<memory.h>
#include<set>
#include<cctype>

#define ll long long
#define LL __int64
#define eps 1e-8

//const ll INF=9999999999999;

#define inf 0xfffffff

using namespace std;


//vector<pair<int,int> > G;
//typedef pair<int,int> P;
//vector<pair<int,int>> ::iterator iter;
//
//map<ll,int>mp;
//map<ll,int>::iterator p;

const int N = 500000  + 10;

int n;

int c[N],x[N];
int ans[N];;

int lowbit(int x) {
	return x&(-x);
}

void update(int i,int val) {
	while(i <= 32005) {
		c[i] += val;
		i += lowbit(i);
	}
}

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

int main() {
	while(scanf("%d",&n) == 1) {
		for(int i=1;i<=n;i++) {
			int y;
			scanf("%d %d",&x[i],&y);
			x[i]++;
		}
		memset(ans,0,sizeof(ans));
		for(int i=1;i<=n;i++) {
			ans[get_sum(x[i])]++;
			
			update(x[i],1);
		}
		for(int i=0;i<n;i++)
			printf("%d\n",ans[i]);
	}
	return 0;
}



/*

5
1 1
5 1
7 1
3 3
5 5

*/

POJ2352 Stars 树状数组简单应用,布布扣,bubuko.com

POJ2352 Stars 树状数组简单应用

原文：http://blog.csdn.net/yitiaodacaidog/article/details/24325331