poj2352——Stars

题意：给你一些按y轴优先排列的坐标点，求这个点的左下方的数有多少个。输出的时候，再转换下即可。

思路：因为的按y轴优先排序的，所以用线段树解决，每次查询(0,x)之间的数，即为这个坐标的左下方的数。并将(x,y)插入线段树。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct node
{
	int left,right,step;
}tree[97000];
int level[15008];
int n;
int find(int index,int left,int right)
{
	if(left<=tree[index].left&&tree[index].right <=right)
		return tree[index].step ;
	int mid =(tree[index].left +tree[index].right )>>1;
	if(mid>=right)
		return find(index*2,left,right);
	else if(left>mid)
		return find(index*2+1,left,right);
	else {
		int m=find(index*2,left,right);
		int n=find(index*2+1,left,right);
		return m+n;
	}
}
void add(int index,int left,int right)
{
	tree[index].step ++;
	if(tree[index].left ==tree[index].right )
		return ;
	int mid=(tree[index].left +tree[index].right )>>1;
	if(mid>=right)
		add(index*2,left,right);
	else 
		add(index*2+1,left,right);
}
void create(int index,int left,int right)
{
	tree[index].left =left;
	tree[index].right =right;
	tree[index].step =0;
	if(left==right)
		return ;
	int mid=(left+right)>>1;
	create(index*2,left,mid);
	create(index*2+1,mid+1,right);
}
int main()
{
	int i,x,y,sum;
	memset(level,0,sizeof(level));
	create(1,0,32000);
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		sum=0;
		sum+=find(1,0,x);
		level[sum]++;
		add(1,0,x);
	}
	for(i=0;i<n;i++)
		printf("%d\n",level[i]);
	return 0;
}