学步园

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

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

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