Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

索引树搞起来,为啥Wrong Answer

Posted by xcwd1598 at 2021-06-12 11:07:06 on Problem 2352
如题,请教大佬
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator