ｐｏｊ２３５２Stars（樹狀數組基礎）

題意：有若干個星星，給出每個星星在二維平面上的坐標（輸入按ｙ遞增順序給出，ｙ相同時按ｘ遞增順序輸出）。定義每個星星的級別為　橫縱坐標均不超過自己的星星的個數（不包括自身）。問級別為０～ｎ－１的星星分別有幾個。

思路：首先將二維轉化為一維。。因為輸入是有順序的，當前星星與後面的星星並沒有關系。對於第ｉ次輸入的星星（橫縱坐標為ｘ，ｙ），只需統計前ｉ－１個中橫坐標小於ｘ的星星的個數。樹狀數組可以很高效的進行區間統計。不過，樹狀數組的下標從１開始，所以當題目中輸入ｘ　＝　０時，要執行ｘ＋＋，相當於所有坐標右移，但相對位置不變。

#include 
#include 

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
,level[i]);
	return 0;
}

區間統計也可以用線段樹實現。。不過樹狀數組跑的比線段樹快，但只要樹狀數組可以實現的線段樹均能實現。

#include 
#include 

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
,level[i]);
	}
	return 0;

}