?id=2352
Stars
Time Limit:1000MSMemory Limit:65536K
Total Submissions:37696Accepted:16419
Description
Astronomers often examine star maps where stars are represented by points on a plane and each star has Cartesian coordinates. Let the level of a star be an amount of the stars that are not higher and not to the right of the given star. Astronomers want to know the distribution of the levels of the stars.
For example, look at the map shown on the figure above. Level of the star number 5 is equal to 3 (it’s formed by three stars with a numbers 1, 2 and 4). And the levels of the stars numbered by 2 and 4 are 1. At this map there are only one star of the level 0, two stars of the level 1, one star of the level 2, and one star of the level 3.You are to write a program that will count the amounts of the stars of each level on a given map.
Input
The first line of the input file contains a number of stars N (1<=N<=15000). The following N lines describe coordinates of stars (two integers X and Y per line separated by a space, 0<=X,Y<=32000). There can be only one star at one point of the plane. Stars are listed in ascending order of Y coordinate. Stars with equal Y coordinates are listed in ascending order of X coordinate.
Output
The output should contain N lines, one number per line. The first line contains amount of stars of the level 0, the second does amount of stars of the level 1 and so on, the last line contains amount of stars of the level N-1.
Sample Input
51 15 17 13 35 5
Sample Output
12110
Hint
This problem has huge input data,use scanf() instead of cin to read data to avoid time limit exceed.
Source
思路：树状数组分析：1 题目是要求出每一个点的左下(正左+正下)有几个星星，那个这个点就是第几层，最后输出0～n-1层的点的个数。比如样列编号为5的星星，，左下有3个星星那么5就处于第三层2 利用树状数组，我们知道树状数组C中，C[i]表示的是原先数组A中的某一段和。题目明确指出输入的时候是按照y值增大的顺序（y相同是x增大），那么我们应该要用什么做为原先的数组A呢，很显然就是X轴，就是A[2]表示x = 2的点的个数。那么当新加入一个点的x值为2的时候，A[2]++，这个时候就是要更新C[2]，C[2+lowbit(2)]…
3 那怎么求某个点的左下有几个星星呢，很显然处在左下的点的x值肯定小于等于当前点的，那么就是相当与树状数组求和，那么整道题的思路就完成4 注意更新树状数组的时候，注意x<=MAXN，不是输入的n。因为更改了A[x]，就要更新C[x] , C[x+lowbit(x)]…
5题目输入的x的坐标可能为0，所以这边我们把所有的x+1，这就避免了TLE
代码：
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;const int MAXN = 32010;int n , ans[MAXN];int treeNum[MAXN];int lowbit(int x){return x&(-x);}int getSum(int x){int sum = 0;while(x){sum += treeNum[x];x -= lowbit(x);}return sum;}void add(int x , int val){while(x < MAXN){treeNum[x] += val;x += lowbit(x);}}int main(){int x , y;while(scanf("%d" , &n) != EOF){memset(treeNum , 0 , sizeof(treeNum));memset(ans , 0 , sizeof(ans));for(int i = 0 ; i < n ; i++){scanf("%d%d" , &x , &y);x++;ans[getSum(x)]++;add(x , 1);}for(int i = 0 ; i < n ; i++)printf("%d\n" , ans[i]);}return 0;}思路：线段树+单点更新分析：1 题目输入的点是按照y的升序，相同y是按照x升序。那么我们就可以知道后面输入的点肯点不会在前面点的左下（包括正左+正下），那么我们只要考虑即可。这样就变成了一个一维的问题，可以利用线段树来做。2 我们知道一个点在另外一个点的左下，那么这个点的x值肯定是小于等于另外一个点。那么新加入一个点就是等价于更新区间[x,x]，然后要求左下有几个点就是询问区间[0,x]的和。3 知道了思路，那么就可以利用线段树求出。这一题由于输入数据是有序的，后面的不影响前面的，那么我们可以在输入之后更新之前求出之前点的level。以此类推求出所有。4 注意x值可能为0，所以根节点区间是[0,MAXN].代码：#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>using namespace std;#define MAXN 32010struct Node{ int left; int right; int sum;};Node node[4*MAXN];int vis[MAXN];/*建立一颗线段树*/void buildTree(int left , int right , int pos){ node[pos].left = left; node[pos].right = right; node[pos].sum = 0; if(left == right)return; int mid = (left+right)>>1; buildTree(left , mid , pos<<1); buildTree(mid+1 , right , (pos<<1)+1);}/*单点更新*/void update(int index , int pos){ if(node[pos].left == node[pos].right){node[pos].sum++;return; } int mid = (node[pos].left+node[pos].right)>>1; if(index <= mid)update(index , pos<<1); elseupdate(index , (pos<<1)+1); node[pos].sum = node[pos<<1].sum + node[(pos<<1)+1].sum;}/*区间查询*/int query(int left , int right , int pos){ if(node[pos].left == left && node[pos].right == right)return node[pos].sum; int mid = (node[pos].left+node[pos].right)>>1; if(right <= mid)return query(left , right , pos<<1); else if(left > mid)return query(left , right , (pos<<1)+1); elsereturn query(left , mid , pos<<1)+query(mid+1 , right , (pos<<1)+1);}int main(){ int Case , n; int x , y; scanf("%d" , &Case); n = Case; buildTree(0 , MAXN , 1); memset(vis , 0 , sizeof(vis)); while(Case–){scanf("%d%d" , &x , &y);vis[query(0 , x , 1)]++;update(x , 1); } for(int i = 0 ; i < n ; i++)printf("%d\n" , vis[i]); return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
启程了，人的智慧才得以发挥。
