POJ 2352 Stars

 1  1 package poj;
 2  2 
 3  3 import java.io.BufferedReader;
 4  4 import java.io.IOException;
 5  5 import java.io.InputStreamReader;
 6  6 import java.util.StringTokenizer;
 7  7 
 8  8 /** 
 9  9  * @ClassName：     POJ_2352.java 
10 10  * @Description：   天文学家经常检查星图，在星图上，星星由平面上的点表示，每颗星星都有笛卡尔坐标。
11 11  *                  某个星星的等级等于高度不大于该星星，且不在此星星右边的星星的数量，天文学家想知道星星的能级分布。 
12 12  *                  你要写一个程序来计算给定地图上每一层星的数量。   
13 13  * @Author：        WangFengyan  
14 14  * @Version：       V1.0   
15 15  * @Date：          2021年5月22日 上午8:49:09 
16 16  * 
17 17  *  分析： 由于y坐标是按升序排列，故星星等级等于在此之前的x坐标小于当前x坐标的星星的个数
18 18  *  可使用Indexed　Tree求星星等级
19 19  */
20 20 
21 21 public class POJ_2352 {
22 22 
23 23 
24 24     static int [] srcArr; 
25 25     static int [] idxTree;
26 26     static int N;
27 27     static int fromIdx;
28 28     static int level ;
29 29     static int [] res;
30 30     public static void main(String[] args) throws IOException {        
31 31         BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
32 32         StringTokenizer st = new StringTokenizer(bf.readLine());
33 33         N = Integer.parseInt(st.nextToken()); 
34 34     
35 35         srcArr = new int[N]; //星星x坐标数组
36 36         res = new int[N];
37 37         for(int i=0;i<N;i++) {
38 38             st = new StringTokenizer(bf.readLine());
39 39             int x = Integer.parseInt(st.nextToken());
40 40             srcArr[i] = x;
41 41         }
42 42         
43 43         init();
44 44         for(int i=0;i<N;i++) {
45 45             level = 0;
46 46             level = query(fromIdx,fromIdx+srcArr[i]-1);
47 47             res[level] += 1 ;
48 48             update(fromIdx+srcArr[i]-1,1);        
49 49         }
50 50         for(int i=0;i<N;i++) {
51 51             System.out.println(res[i]);
52 52         }        
53 53     }
54 54 
55 55     public static void init() {
56 56         int k=0;
57 57         while((1<<k)<srcArr.length) {
58 58             k++;
59 59         }
60 60         idxTree = new int[1<<(k+1)];
61 61         fromIdx = 1<<k;
62 62         for(int i=0,j=0;i<idxTree.length && j<srcArr.length;i++) {
63 63             idxTree[i] = 0;
64 64         }
65 65     }
66 66     
67 67     public static void update(int idx, int target) {
68 68         while(idx>0) {
69 69             idxTree[idx] = idxTree[idx] + target;
70 70             idx = idx >> 1;
71 71         }
72 72     }
73 73     
74 74     public static int query(int s,int e) {
75 75         int res=0;
76 76         while(s<=e) {
77 77             if((s&1)==1) {
78 78                 res = res + idxTree[s];
79 79             }
80 80             
81 81             if((e&1)==0) {
82 82                 res = res + idxTree[e];
83 83             }
84 84             
85 85             s = (s+1) >> 1;
86 86             e = (e-1) >> 1;
87 87         }
88 88         return res;
89 89     }
90 90     
91 91 }
92 92 
93 93 
94 94