| ||||||||||
| 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