BOJ. Josephus problem(2) (1168)

import java.util.*;
import java.io.*;

public class Main {
	static BufferedReader br;
	static int[] seg;
	static int[] orig;
	public static void main(String[] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int[] line = getArr();
		int n = line[0], k = line[1];
		int curLen = n, order = 1;
		sb.append("<");

		seg = new int[1 << (int)Math.ceil(Math.log(n) / Math.log(2)) + 1];
		init(seg, 1, n, 1);

		for(int i = 0; i < n; i++) {
			order = (order + k - 1) % curLen;
			if(order == 0) order = curLen;
			int val = get(seg, 1, n, 1, order);
			delete(seg, 1, n, 1, val);
			sb.append(val).append(", ");
			curLen--;
		}
		sb.setLength(sb.length() - 2);
		sb.append(">");
		print(sb);
	}

	static int init(int[] seg, int start, int end, int idx) {
		if(start == end) return seg[idx] = 1;
		int mid = (start+end)>>1;
		return seg[idx] = init(seg, start, mid, idx<<1) + init(seg, mid+1, end, idx<<1|1);
	}

	static int get(int[] seg, int left, int right, int idx, int nth) {
		if(left == right) return left;
		int mid = (left+right)>>1;
		if(seg[idx<<1] >= nth) return get(seg, left, mid, idx<<1, nth);
		else return get(seg, mid + 1, right, idx<<1|1, nth - seg[idx<<1]);
	}

	static void delete(int[] seg, int left, int right, int idx, int target) {
		if(right < target || target < left) return;
		seg[idx]--;
		if(left == right) return;
		int mid = (left + right)>>1;
		delete(seg, left, mid, idx<<1, target);
		delete(seg, mid+1, right, idx<<1|1, target);
	}

	static int toi(String s) { return Integer.parseInt(s); }
	static String[] getLine() throws IOException { return br.readLine().split(" "); }
	static int[] getArr() throws IOException { return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray(); }
	static <T> void print(T s) { System.out.print(s); }
	static <T> void println(T s) { System.out.println(s); }
}