# Poj Solution 1591

```http://poj.org/problem?id=1591

//* @author: SmilingWang
import java.util.*;

public class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int n;
int left;
int i, j;
int count = 1;
while(in.hasNext()){
n = in.nextInt();
left = in.nextInt();
BinarySearchTreeWithRank bt = new BinarySearchTreeWithRank();
for(i = 1; i <= n; i++){
bt.insert(i);
}
for(i = 0; i < 20; i++){
}
j = 0;
//bt.inorder(bt.root);
//System.out.println();
while(j < list.size()){
int cut = list.get(j);
int p = cut, q = 0;
int size0 = bt.size;
while(p <= size0){
if(bt.findKth(p-q) != -1){
bt.remove(bt.findKth(p-q));
q++;
}
//System.out.println(p +" : " + bt.size + " : " + q);
p += cut;
if(bt.size == left){
break;
}
//bt.inorder(bt.root);
//System.out.println();
}
if(bt.size == left){
break;
}
j++;
}
System.out.println("Selection #" + count++);
for(i = 1; i < left; i++){
System.out.print(bt.findKth(i) + " ");
}
System.out.println(bt.findKth(left));
System.out.println();
}
}
}

class BinarySearchTreeWithRank{

BinaryNodeWithRank root;
int size;

class BinaryNodeWithRank{
int v;
BinaryNodeWithRank left, right;
int rank;
int height;
}

public BinaryNodeWithRank insert(int v, BinaryNodeWithRank t){
if(t == null){
t = new BinaryNodeWithRank();
t.v = v;
t.rank = 1;
return t;
}
if(v < t.v){
t.left = insert(v, t.left);
t.rank ++;

if(height(t.left) - height(t.right) == 2){
if(v < t.left.v){
t =  rotateWithLeftChild(t);
}
else{
t = doubleWithLeftChild(t);
}
}
}
else if(v > t.v){
t.right = insert(v, t.right);
if(height(t.right) - height(t.left) == 2){
if(v > t.right.v){
t = rotateWithRightChild(t);
}
else{
t = doubleWithRightChild(t);
}
}
}
t.height = Math.max(height(t.left), height(t.right)) + 1;
return t;
}

private int height(BinaryNodeWithRank t){
return t == null ? -1 : t.height;
}

public void insert(int v){
root = insert(v, root);
size++;
}
public void remove(int v){
root = remove(v, root);
size--;
}
public int findKth(int k){
return findKth(k, root);
}
public int findKth(int k, BinaryNodeWithRank t){
if(t == null){
return -1;
}
if(t.rank < k){
return findKth(k - t.rank, t.right);
}
else if(t.rank > k){
return findKth(k, t.left);
}
else{
return t.v;
}
}

public BinaryNodeWithRank remove(int v, BinaryNodeWithRank t){
if(v < t.v){
t.left = remove(v, t.left);
t.rank--;
}
else if(v > t.v){
t.right = remove(v, t.right);
}
else if(t.left != null && t.right != null){
t.v = findMin(t.right).v;
t.right = removeMin( t.right );
}
else{
return (t.left == null ? t.right : t.left);
}
return t;
}

private BinaryNodeWithRank removeMin(BinaryNodeWithRank tt){
BinaryNodeWithRank t = tt;
if( t.left == null )
return t.right;

t.left = removeMin( t.left );
t.rank--;
return t;
}

public BinaryNodeWithRank findMin(BinaryNodeWithRank t){
while(t.left != null){
t = t.left;
}
return t;
}
public void inorder(BinaryNodeWithRank t){
if(t != null){
inorder(t.left);
System.out.print(t.v +" ");
inorder(t.right);
}
}

private BinaryNodeWithRank rotateWithLeftChild(BinaryNodeWithRank k2){
BinaryNodeWithRank k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
k1.height = Math.max(height(k1.left), k2.height) + 1;
if(k2.left == null){
k2.rank = 1;
}
else{
k2.rank = k2.left.rank + 1;
}
return k1;
}
private BinaryNodeWithRank rotateWithRightChild(BinaryNodeWithRank k2){
BinaryNodeWithRank k1 = k2.right;
k2.right = k1.left;
k1.left  = k2;
k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
k1.height = Math.max(height(k1.right), k2.height) + 1;
k1.rank += k2.rank;
return k1;
}
private BinaryNodeWithRank doubleWithLeftChild(BinaryNodeWithRank k3){
k3.left = rotateWithRightChild(k3.left);

return rotateWithLeftChild(k3);
}
private BinaryNodeWithRank doubleWithRightChild(BinaryNodeWithRank k3){
k3.right = rotateWithLeftChild(k3.right);

return rotateWithRightChild(k3);
}
}

```
This entry was posted in poj. Bookmark the permalink.