Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
索引树搞起来,为啥Wrong Answer如题,请教大佬 package IndexTree; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class POJ2352 { static StringTokenizer st; static int N, max; static Star[] starrArray; static int[] tree, ans; public static void main(String[] args) throws Throwable { // TODO Auto-generated method stub BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); starrArray = new Star[N]; for (int i = 0; i < N; i++) { st = new StringTokenizer(br.readLine()); int tmpX = Integer.parseInt(st.nextToken()); int tmpY = Integer.parseInt(st.nextToken()); Star tmpStar = new Star(tmpX, tmpY); starrArray[i] = tmpStar; max = Math.max(max, tmpX); } int L = 1; while (L < max + 1) { L = L + L; } tree = new int[2 * L]; ans = new int[2 * L ]; for (int i = 0; i < starrArray.length; i++) { int fromIndex = starrArray[i].x + L - 1; int getNum = query(L, fromIndex); ans[getNum] = ans[getNum] + 1; update(starrArray[i].x + L, getNum + 1); } for(int i=0;i<N;i++) { System.out.println(ans[i]); } } static int query(int start, int end) { int rnt = 0; while (start <= end) { if (start % 2 == 1) { rnt = rnt + tree[start]; } if (start % 2 == 0) { rnt = rnt + tree[end]; } start = (start + 1) >> 1; end = (end - 1) >> 1; } return rnt; } static void update(int index, int value) { while (index > 0) { tree[index] = tree[index] + 1; index = index >> 1; } } static class Star { int x; int y; public Star(int x, int y) { super(); this.x = x; this.y = y; } } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator