学步园

http://poj.org/problem?id=2352

题意：有若干个星星，给出每个星星在二维平面上的坐标（输入按ｙ递增顺序给出，ｙ相同时按ｘ递增顺序输出）。定义每个星星的级别为　横纵坐标均不超过自己的星星的个数（不包括自身）。问级别为０～ｎ－１的星星分别有几个。

思路：首先将二维转化为一维。。因为输入是有顺序的，当前星星与后面的星星并没有关系。对于第ｉ次输入的星星（横纵坐标为ｘ，ｙ），只需统计前ｉ－１个中横坐标小于ｘ的星星的个数。树状数组可以很高效的进行区间统计。不过，树状数组的下标从１开始，所以当题目中输入ｘ　＝　０时，要执行ｘ＋＋，相当于所有坐标右移，但相对位置不变。

#include <stdio.h>
#include <string.h>

const int maxn = 32001;
int level[maxn];
int c[maxn];

int Lowbit(int x)
{
	return x&(-x);
}
int sum(int end)
{
	int s = 0;
	while(end > 0)
	{
		s += c[end];
		end -= Lowbit(end);
	}
	return s;
}

void update(int pos)
{
	while(pos <= maxn)
	{
		c[pos]++;
		pos += Lowbit(pos);
	}
}

int main()
{
	int n,x,y;
	scanf("%d",&n);
	memset(level,0,sizeof(level));
	memset(c,0,sizeof(c));

	for(int i = 0; i < n; i++)
	{
		scanf("%d %d",&x,&y);
		level[sum(x+1)] ++;
		update(x+1);
	}
	for(int i = 0; i < n; i++)
		printf("%d\n",level[i]);
	return 0;
}

区间统计也可以用线段树实现。。不过树状数组跑的比线段树快，但只要树状数组可以实现的线段树均能实现。

#include <stdio.h>
#include <string.h>

const int maxn = 32002;

struct line
{
	int l;
	int r;
	int num;
}tree[maxn<<2];

int level[maxn];

void build(int v, int l, int r)
{
	tree[v].l = l;
	tree[v].r = r;
	tree[v].num = 0;
	if(l == r)
		return;
	int mid = (l+r)>>1;
	build(v*2,l,mid);
	build(v*2+1,mid+1,r);
}
//查询区间1~x
int query(int v, int l, int r)
{
	if(tree[v].l == l && tree[v].r == r)
		return tree[v].num;

	int mid = (tree[v].l + tree[v].r)>>1;
	if(r <= mid)
		return query(v*2,l,r);
	else
	{
		if(l > mid)
			return query(v*2+1,l,r);
		else
			return query(v*2,l,mid) + query(v*2+1,mid+1,r);
	}
}
//单点更新 pos
void update(int v, int pos)
{
	tree[v].num++;
	if(tree[v].l == tree[v].r)
		return;
	int mid = (tree[v].l + tree[v].r)>>1;
	if(pos <= mid)
		update(v*2,pos);
	else update(v*2+1,pos);
}

int main()
{
	int n;
	int x,y;
	memset(level,0,sizeof(level));

	scanf("%d",&n);
	build(1,1,32001);	//建树

	for(int i = 1; i <= n; i++)
	{
		scanf("%d %d",&x,&y);
		x++;
		level[ query(1,1,x) ]++;
		update(1,x);
	}

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

}