import java.util.*; import java.util.zip.*; import java.util.List; import java.util.regex.*; import java.util.concurrent.*; import java.util.concurrent.atomic.*; import java.util.concurrent.locks.*; import javax.swing.*; import javax.swing.event.*; import javax.swing.text.*; import javax.swing.table.*; import java.io.*; import java.net.*; import java.lang.reflect.*; import java.lang.ref.*; import java.lang.management.*; import java.security.*; import java.security.spec.*; import java.awt.*; import java.awt.event.*; import java.awt.image.*; import javax.imageio.*; import java.math.*; // see: https://en.wikipedia.org/wiki/Order_statistic_tree class main { static class LogNArray extends RandomAccessAbstractList { private transient Entry root; /** * The number of entries in the tree */ //private transient int size = 0; /** * The number of structural modifications to the tree. */ private transient int modCount = 0; // Query Operations public int size() { return root == null ? 0 : root.size; } public boolean contains(Object value) { for (Entry e = getFirstEntry(); e != null; e = successor(e)) if (eq(value, e.value)) return true; return false; } public A get(int idx) { Entry p = getEntry(idx); return p == null ? null : p.value; } int subTreeSize(Entry e) { return e == null ? 0 : e.size; } final Entry getEntry(int idx) { if (idx < 0 || idx >= size()) throw new IndexOutOfBoundsException(idx + " / " + size()); Entry p = root; while (true) { int sizeLeft = subTreeSize(p.left); if (idx < sizeLeft) { p = p.left; continue; } idx -= sizeLeft; if (idx == 0) return p; idx--; p = p.right; } } /*public A put(Int key, A value) { Entry t = root; if (t == null) { compare(key, key); // type (and possibly null) check root = new Entry<>(key, value, null); //size = 1; modCount++; return null; } int cmp; Entry parent; // split comparator and comparable paths Comparator cpr = comparator; if (cpr != null) { do { parent = t; cmp = cpr.compare(key, t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else return t.setValue(value); } while (t != null); } else { if (key == null) throw new NullPointerException(); @SuppressWarnings("unchecked") Comparable k = (Comparable) key; do { parent = t; cmp = k.compareTo(t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else return t.setValue(value); } while (t != null); } Entry e = new Entry<>(key, value, parent); if (cmp < 0) parent.left = e; else parent.right = e; fixAfterInsertion(e); //size++; modCount++; return null; }*/ /*public A remove(int idx) { Entry p = getEntry(key); if (p == null) return null; A oldValue = p.value; deleteEntry(p); return oldValue; }*/ public void clear() { modCount++; //size = 0; root = null; } // Red-black mechanics private static final boolean RED = false; private static final boolean BLACK = true; /** * Node in the Tree. Doubles as a means to pass key-value pairs back to * user (see Map.Entry). */ static final class Entry { int size = 1; // entry count of subtree //Int key; A value; Entry left; Entry right; Entry parent; boolean color = BLACK; /** * Make a new cell with given value and parent, and with * {@code null} child links, size 1, and BLACK color. */ Entry(A value, Entry parent) { this.value = value; this.parent = parent; } } final Entry getFirstEntry() { Entry p = root; if (p != null) while (p.left != null) p = p.left; return p; } final Entry getLastEntry() { Entry p = root; if (p != null) while (p.right != null) p = p.right; return p; } static LogNArray.Entry successor(Entry t) { if (t == null) return null; else if (t.right != null) { Entry p = t.right; while (p.left != null) p = p.left; return p; } else { Entry p = t.parent; Entry ch = t; while (p != null && ch == p.right) { ch = p; p = p.parent; } return p; } } static Entry predecessor(Entry t) { if (t == null) return null; else if (t.left != null) { Entry p = t.left; while (p.right != null) p = p.right; return p; } else { Entry p = t.parent; Entry ch = t; while (p != null && ch == p.left) { ch = p; p = p.parent; } return p; } } /** * Balancing operations. * * Implementations of rebalancings during insertion and deletion are * slightly different than the CLR version. Rather than using dummy * nilnodes, we use a set of accessors that deal properly with null. They * are used to avoid messiness surrounding nullness checks in the main * algorithms. */ private static boolean colorOf(Entry p) { return (p == null ? BLACK : p.color); } private static Entry parentOf(Entry p) { return (p == null ? null: p.parent); } private static void setColor(Entry p, boolean c) { if (p != null) p.color = c; } private static Entry leftOf(Entry p) { return (p == null) ? null: p.left; } private static Entry rightOf(Entry p) { return (p == null) ? null: p.right; } /** From CLR */ private void rotateLeft(Entry p) { if (p != null) { Entry r = p.right; p.right = r.left; if (r.left != null) r.left.parent = p; r.parent = p.parent; if (p.parent == null) root = r; else if (p.parent.left == p) p.parent.left = r; else p.parent.right = r; r.left = p; p.parent = r; } } /** From CLR */ private void rotateRight(Entry p) { if (p != null) { Entry l = p.left; p.left = l.right; if (l.right != null) l.right.parent = p; l.parent = p.parent; if (p.parent == null) root = l; else if (p.parent.right == p) p.parent.right = l; else p.parent.left = l; l.right = p; p.parent = l; } } /** From CLR */ private void fixAfterInsertion(Entry x) { x.color = RED; while (x != null && x != root && x.parent.color == RED) { if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { Entry y = rightOf(parentOf(parentOf(x))); if (colorOf(y) == RED) { setColor(parentOf(x), BLACK); setColor(y, BLACK); setColor(parentOf(parentOf(x)), RED); x = parentOf(parentOf(x)); } else { if (x == rightOf(parentOf(x))) { x = parentOf(x); rotateLeft(x); } setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); rotateRight(parentOf(parentOf(x))); } } else { Entry y = leftOf(parentOf(parentOf(x))); if (colorOf(y) == RED) { setColor(parentOf(x), BLACK); setColor(y, BLACK); setColor(parentOf(parentOf(x)), RED); x = parentOf(parentOf(x)); } else { if (x == leftOf(parentOf(x))) { x = parentOf(x); rotateRight(x); } setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); rotateLeft(parentOf(parentOf(x))); } } } root.color = BLACK; } /** * Delete node p, and then rebalance the tree. */ private void deleteEntry(Entry p) { modCount++; //size--; // If strictly internal, copy successor's element to p and then make p // point to successor. if (p.left != null && p.right != null) { Entry s = successor(p); p.value = s.value; p = s; } // p has 2 children // Start fixup at replacement node, if it exists. Entry replacement = (p.left != null ? p.left : p.right); if (replacement != null) { // Link replacement to parent replacement.parent = p.parent; if (p.parent == null) root = replacement; else if (p == p.parent.left) p.parent.left = replacement; else p.parent.right = replacement; // Null out links so they are OK to use by fixAfterDeletion. p.left = p.right = p.parent = null; // Fix replacement if (p.color == BLACK) fixAfterDeletion(replacement); } else if (p.parent == null) { // return if we are the only node. root = null; } else { // No children. Use self as phantom replacement and unlink. if (p.color == BLACK) fixAfterDeletion(p); if (p.parent != null) { if (p == p.parent.left) p.parent.left = null; else if (p == p.parent.right) p.parent.right = null; p.parent = null; } } } /** From CLR */ private void fixAfterDeletion(Entry x) { while (x != root && colorOf(x) == BLACK) { if (x == leftOf(parentOf(x))) { Entry sib = rightOf(parentOf(x)); if (colorOf(sib) == RED) { setColor(sib, BLACK); setColor(parentOf(x), RED); rotateLeft(parentOf(x)); sib = rightOf(parentOf(x)); } if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) { setColor(sib, RED); x = parentOf(x); } else { if (colorOf(rightOf(sib)) == BLACK) { setColor(leftOf(sib), BLACK); setColor(sib, RED); rotateRight(sib); sib = rightOf(parentOf(x)); } setColor(sib, colorOf(parentOf(x))); setColor(parentOf(x), BLACK); setColor(rightOf(sib), BLACK); rotateLeft(parentOf(x)); x = root; } } else { // symmetric Entry sib = leftOf(parentOf(x)); if (colorOf(sib) == RED) { setColor(sib, BLACK); setColor(parentOf(x), RED); rotateRight(parentOf(x)); sib = leftOf(parentOf(x)); } if (colorOf(rightOf(sib)) == BLACK && colorOf(leftOf(sib)) == BLACK) { setColor(sib, RED); x = parentOf(x); } else { if (colorOf(leftOf(sib)) == BLACK) { setColor(rightOf(sib), BLACK); setColor(sib, RED); rotateLeft(sib); sib = leftOf(parentOf(x)); } setColor(sib, colorOf(parentOf(x))); setColor(parentOf(x), BLACK); setColor(leftOf(sib), BLACK); rotateRight(parentOf(x)); x = root; } } } setColor(x, BLACK); } /** * Finds the level down to which to assign all nodes BLACK. This is the * last `full' level of the complete binary tree produced by buildTree. * The remaining nodes are colored RED. (This makes a `nice' set of * color assignments wrt future insertions.) This level number is * computed by finding the number of splits needed to reach the zeroeth * node. * * @param size the (non-negative) number of keys in the tree to be built */ private static int computeRedLevel(int size) { return 31 - Integer.numberOfLeadingZeros(size + 1); } } static boolean eq(Object a, Object b) { return a == null ? b == null : a == b || b != null && a.equals(b); } static String str(Object o) { return o == null ? "null" : o.toString(); } static String str(char[] c) { return new String(c); } abstract static class RandomAccessAbstractList extends AbstractList implements RandomAccess { } }