Первая строка будет целым числом T, которое является количеством тестовых случаев.Для каждого теста в первой строке будут два целых числа n и m.Затем следуют n строк, каждая строка будет в одном из следующих случаев:
I x: вставить x.введите число x.
A x: Добавить х.увеличьте каждое число в последовательности на x.
S x: вычтите x.уменьшите каждое число в последовательности на x, а затем удалите числа, которые меньше m.
Q x: запрос x.выведите максимальное число k в этой последовательности.
Ввод
Первая строка будет целым числом T, котороеколичество тестовых случаев.Для каждого теста в первой строке будут два целых числа n и m.Затем, после n строк, каждая строка будет в одном из следующих случаев:
Выход:
Для каждого «запроса» выведитеМаксимальное число k в этой последовательности.Если длина последовательности меньше k, выведите «-1».Наконец, выведите количество элементов, которые мы удалили.
Я пытаюсь использовать обратный порядок обхода по порядку, чтобы найти первое (наибольшее) число и развернуть его до корня.Затем я поместил указатель root на его правый дочерний элемент (реализован в update).
Реализация Splay скопирована из Интернета, а авторские права принадлежат Princeton Uni.(Thx)
Вот мой код, и я получаю RTR ошибку во время выполнения.Спасибо за чтение.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.Stack;
import java.util.StringTokenizer;
public class Splay{
private Node root; // root of the BST
public static int m = 0;
public static int baseNum = 0;
private int delNum = 0;
public static void main(String[] args) {
parse();
}
private static void parse() {
try {
InputReader inputReader = new InputReader(System.in);
PrintWriter out = new PrintWriter(System.out);
int case_num = inputReader.nextInt();
while (case_num-- > 0) {
Splay splay = new Splay();
int n = inputReader.nextInt();
m = inputReader.nextInt();
while (n-- > 0) {
String s = inputReader.next();
int value = inputReader.nextInt();
switch (s) {
case "I":
splay.put(value - baseNum);
break;
case "A":
baseNum += value;
break;
case "S":
baseNum -= value;
splay.update();
break;
case "Q":
Integer res = splay.find(value);
System.out.println(res == null ? "-1" : res + baseNum);
break;
default:
System.out.println("-1");
}
}
System.out.println(splay.delNum);
}
inputReader.close();
out.close();
} catch (Exception e) {
System.err.println("Error when paring");
}
}
private Integer find(int k) {
if (size(root) < k) {
return null;
}
/* After call size, the size of each node has stored in itself*/
Node curNode = root;
while (true) {
// if (curNode.left != null) {
//// System.out.println(" left = " + curNode.left);
// }
// if (curNode.right != null) {
//// System.out.println(" right = " + curNode.right + "right.size = " + curNode.right.size);
// }
if (curNode.right != null && k <= curNode.right.size) {
curNode = curNode.right;
} else {
k -= curNode.right == null ? 1 : curNode.right.size + 1;
// System.out.println("k = " + k);
if (k == 0) {
return curNode.key;
} else {
curNode = curNode.left;
}
}
}
}
private void update() {
Integer integer = inOrderByStack();
if (integer == null) {
return;
}
// System.out.println("integer = " + integer);
root = splay(root, integer);
// System.out.println("delete " + root.key);
delNum += size(root.left) + 1;
root = root.right;
}
/*
Do some modify to traversal right child first.
*/
private Integer inOrderByStack() {
int max = m - baseNum;
Stack<Node> stack = new Stack<>();
Node current = root;
while (current != null || !stack.isEmpty()) {
while (current != null) {
stack.push(current);
current = current.right;
}
if (!stack.isEmpty()) {
current = stack.pop();
if (current.key < max) {
return current.key;
}
current = current.left;
}
}
return null;
}
// BST helper node data type
private class Node {
private int key; // key
private int size;
private Node left, right; // left and right subtrees
public int getSize() {
return size;
}
public Node(int key) {
this.key = key;
}
@Override
public String toString() {
return "[ " + key + " ]";
}
}
// return value associated with the given key
// if no such value, return null
public int get(int key) {
root = splay(root, key);
int cmp = Integer.compare(key, root.key);
if (cmp == 0) return root.key;
else return -1;
}
/***************************************************************************
* Splay tree insertion.
***************************************************************************/
public void put(int key) {
// splay key to root
if (root == null) {
root = new Node(key);
return;
}
root = splay(root, key);
int cmp = Integer.compare(key, root.key);
// Insert new node at root
if (cmp < 0) {
Node n = new Node(key);
n.left = root.left;
n.right = root;
root.left = null;
root = n;
} else if (cmp > 0) { // Insert new node at root
Node n = new Node(key);
n.right = root.right;
n.left = root;
root.right = null;
root = n;
} else { // It was a duplicate key. Simply replace the value
root.key = key;
}
}
/***************************************************************************
* Splay tree deletion.
***************************************************************************/
/* This splays the key, then does a slightly modified Hibbard deletion on
* the root (if it is the node to be deleted; if it is not, the key was
* not in the tree). The modification is that rather than swapping the
* root (call it node A) with its successor, it's successor (call it Node B)
* is moved to the root position by splaying for the deletion key in A's
* right subtree. Finally, A's right child is made the new root's right
* child.
*/
public void remove(int key) {
if (root == null) return; // empty tree
root = splay(root, key);
int cmp = Integer.compare(key, root.key);
if (cmp == 0) {
if (root.left == null) {
root = root.right;
}
else {
Node x = root.right;
root = root.left;
splay(root, key);
root.right = x;
}
}
// else: it wasn't in the tree to remove
}
/***************************************************************************
* Splay tree function.
* **********************************************************************/
// splay key in the tree rooted at Node h. If a node with that key exists,
// it is splayed to the root of the tree. If it does not, the last node
// along the search path for the key is splayed to the root.
private Node splay(Node h, int key) {
if (h == null) return null;
int cmp1 = Integer.compare(key, root.key);
if (cmp1 < 0) {
// key not in tree, so we're done
if (h.left == null) {
return h;
}
int cmp2 = Integer.compare(key, h.left.key);
if (cmp2 < 0) {
h.left.left = splay(h.left.left, key);
h = rotateRight(h);
}
else if (cmp2 > 0) {
h.left.right = splay(h.left.right, key);
if (h.left.right != null)
h.left = rotateLeft(h.left);
}
if (h.left == null) return h;
else return rotateRight(h);
}
else if (cmp1 > 0) {
// key not in tree, so we're done
if (h.right == null) {
return h;
}
int cmp2 = Integer.compare(key, h.right.key);
if (cmp2 < 0) {
h.right.left = splay(h.right.left, key);
if (h.right.left != null)
h.right = rotateRight(h.right);
}
else if (cmp2 > 0) {
h.right.right = splay(h.right.right, key);
h = rotateLeft(h);
}
if (h.right == null) return h;
else return rotateLeft(h);
}
else return h;
}
/***************************************************************************
* Helper functions.
***************************************************************************/
// height of tree (1-node tree has height 0)
public int height() { return height(root); }
private int height(Node x) {
if (x == null) return -1;
return 1 + Math.max(height(x.left), height(x.right));
}
public int size() {
return size(root);
}
private int size(Node x) {
if (x == null) return 0;
x.size = 1 + size(x.left) + size(x.right);
return x.size;
}
// right rotate
private Node rotateRight(Node h) {
Node x = h.left;
h.left = x.right;
x.right = h;
return x;
}
// left rotate
private Node rotateLeft(Node h) {
Node x = h.right;
h.right = x.left;
x.left = h;
return x;
}
static class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
public long nextLong() {
return Long.parseLong(next());
}
public double nextDouble() {
return Double.parseDouble(next());
}
public char[] nextCharArray() {
return next().toCharArray();
}
public boolean hasNext() {
try {
String string = reader.readLine();
if (string == null) {
return false;
}
tokenizer = new StringTokenizer(string);
return tokenizer.hasMoreTokens();
} catch (IOException e) {
return false;
}
}
public BigInteger nextBigInteger() {
return new BigInteger(next());
}
public BigDecimal nextBigDecinal() {
return new BigDecimal(next());
}
public void close() {
try {
reader.close();
} catch (IOException e) {
System.err.println("close err");
}
tokenizer = null;
}
}
}