Cartesian Tree Algorithm
introduce by Vuillemin (1980) in the context of geometric range searching data structures, Cartesian trees have also been used in the definition of the treap and randomized binary search tree data structures for binary search problems. In computer science, a Cartesian tree is a binary tree derived from a sequence of numbers; it can be uniquely specify from the property that it is heap-ordered and that a symmetric (in-order) traversal of the tree returns the original sequence. Gabow, Bentley & Tarjan (1984) and subsequent writers followed the definition here in which a Cartesian tree is specify from a sequence; this change generalizes the geometric setting of Vuillemin to let sequences other than the sorted order of X-coordinates, and lets the Cartesian tree to be apply to non-geometric problems as well. The name is derived from the Cartesian coordinate system for the airplane: in Vuillemin's version of this structure, as in the two-dimensional range searching application discussed above, a Cartesian tree for a point set has the sorted order of the points by their X-coordinates as its symmetric traversal order, and it has the heap property according to the Y-coordinates of the points. Cartesian trees were introduced and named by Vuillemin (1980).
/*************************************************************************************
Cartesian tree. Can be used as a balanced binary search tree.
O(logN) on operation.
Based on problem 2782 from informatics.mccme.ru:
http://informatics.mccme.ru/mod/statements/view3.php?chapterid=2782
*************************************************************************************/
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <utility>
#include <iomanip>
using namespace std;
const int mod = 1000 * 1000 * 1000;
struct node {
int x, y;
node *l, *r;
node(int new_x, int new_y) {
x = new_x; y = new_y;
l = NULL; r = NULL;
}
};
typedef node * pnode;
void merge(pnode &t, pnode l, pnode r) {
if (l == NULL)
t = r;
else if (r == NULL)
t = l;
else if (l->y > r->y) {
merge(l->r, l->r, r);
t = l;
}
else {
merge(r->l, l, r->l);
t = r;
}
}
void split(pnode t, int x, pnode &l, pnode &r) {
if (t == NULL)
l = r = NULL;
else if (t->x > x) {
split(t->l, x, l, t->l);
r = t;
}
else {
split(t->r, x, t->r, r);
l = t;
}
}
void add(pnode &t, pnode a) {
if (t == NULL)
t = a;
else if (a->y > t->y) {
split(t, a->x, a->l, a->r);
t = a;
}
else {
if (t->x < a->x)
add(t->r, a);
else
add(t->l, a);
}
}
int next(pnode t, int x) {
int ans = -1;
while (t != NULL) {
if (t->x < x)
t = t->r;
else {
if (ans == -1 || ans > t->x)
ans = t->x;
t = t->l;
}
}
return ans;
}
int n, ans, x;
char qt, prev_qt;
pnode root = NULL, num;
int main() {
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
scanf("%d\n", &n);
for (int i = 1; i <= n; i++) {
scanf("%c %d\n", &qt, &x);
if (qt == '+') {
if (prev_qt == '?')
x = (x + ans) % mod;
num = new node(x, rand());
add(root, num);
}
else {
ans = next(root, x);
printf("%d\n", ans);
}
prev_qt = qt;
}
return 0;
}
