#include <bits/stdc++.h>
using namespace std;
struct persistantTab
{
short size = 1, countains = 0;
struct Node
{
char letter;
Node *left = nullptr;
Node *right = nullptr;
Node() : letter(0), left(nullptr), right(nullptr) {}
Node(char l) : letter(l), left(nullptr), right(nullptr) {}
Node(char l, Node *n, Node *p) : letter(l), left(n), right(p) {}
Node(const Node *other) : letter(other->letter), left(other->left), right(other->right) {}
~Node()
{
if (left)
delete left;
if (right)
delete right;
}
};
Node *head = new Node(); // Root of the tree
persistantTab() : head(new Node()), size(1), countains(0) {}
persistantTab(Node *h, int s, int c) : head(h), size(s), countains(c) {}
persistantTab addLetter(char L) const
{
persistantTab newTab(head, size, countains + 1);
if (newTab.countains > newTab.size)
{
newTab.head = new Node(0, head, nullptr);
newTab.size *= 2;
}
// function<Node *(Node *, char, int, int, int)> addL = [&](Node *node, char l, int pos, int low, int high) -> Node *
// {
// if (!node)
// node = new Node();
// if (high - low == 1)
// {
// node->letter = l; // Set the letter at the position
// return node; // Return the updated node
// }
// Node *newNode = new Node(node);
// int mid = (low + high) / 2;
// if (pos < mid)
// // Go left
// newNode->left = addL(node->left, l, pos, low, mid);
// else
// // Go right
// newNode->right = addL(node->right, l, pos, mid, high);
// return newNode;
// };
function<Node *(Node *, char, int, int, int)> addLIter = [](Node *node, char l, int pos, int low, int high) -> Node *
{
// Pile pour mémoriser le chemin parcouru (nœuds + intervalles)
stack<tuple<Node *, bool, int, int>> stk;
if (!node)
node = new Node();
Node *current = node;
int clow = low, chigh = high;
// Descente jusqu'à la feuille
while (chigh - clow > 1)
{
int mid = (clow + chigh) / 2;
stk.emplace(current, pos >= mid, clow, chigh); // bool: true => droite, false => gauche
if (pos < mid)
{
if (!current->left)
current->left = new Node();
current = current->left;
chigh = mid;
}
else
{
if (!current->right)
current->right = new Node();
current = current->right;
clow = mid;
}
}
// Mise à jour de la feuille
Node *updated = new Node(*current);
updated->letter = l;
// Remontée en créant de nouveaux nœuds
while (!stk.empty())
{
auto [parent, isRight, plow, phigh] = stk.top();
stk.pop();
Node *copy = new Node(*parent);
if (isRight)
copy->right = updated;
else
copy->left = updated;
updated = copy;
}
return updated;
};
newTab.head = addLIter(newTab.head, L, newTab.countains - 1, 0, newTab.size);
return newTab;
}
char getLetter(int pos) const
{
// function<char(Node *, int, int, int)> getL = [&](Node *node, int p, int low, int high) -> char
// {
// if (!node)
// return 0; // If the node is null, return 0 (no letter)
// if (high - low == 1)
// return node->letter; // Return the letter at the position
// int mid = (low + high) / 2;
// if (p < mid)
// // Go left
// return getL(node->left, p, low, mid);
// else
// // Go right
// return getL(node->right, p, mid, high);
// };
function<char(Node *, int, int, int)> getLIter = [](Node *node, int p, int low, int high) -> char
{
while (node)
{
if (high - low == 1)
return node->letter;
int mid = (low + high) / 2;
if (p < mid)
{
// Aller à gauche
node = node->left;
high = mid;
}
else
{
// Aller à droite
node = node->right;
low = mid;
}
}
return 0; // Si on atteint un nœud nul
};
if (pos < 0 || pos >= countains)
return 0; // If the position is out of bounds, return 0
return getLIter(head, pos, 0, size);
}
};
vector<persistantTab> tabs;
void Init()
{
// cout << "Init" << endl;
tabs.push_back(persistantTab());
// tabs.back().show();
// cout << "Init done" << endl;
}
void TypeLetter(char L)
{
// cout << "TypeLetter: " << L << endl;
tabs.push_back(tabs.back().addLetter(L));
// tabs.back().show();
// cout << "TypeLetter done" << endl;
}
void UndoCommands(int U)
{
// cout << "UndoCommands: " << U << endl;
tabs.push_back(tabs[tabs.size() - 1 - U]);
// tabs.back().show();
// cout << "UndoCommands done" << endl;
}
char GetLetter(int P)
{
return tabs.back().getLetter(P);
}
#ifdef HOME
int main()
{
Init();
int tmp;
int cmd_num;
tmp = scanf("%d", &cmd_num);
assert(tmp == 1);
int i;
for (i = 0; i < cmd_num; i++)
{
char cmd;
tmp = scanf(" %c", &cmd);
assert(tmp == 1);
if (cmd == 'T')
{
char letter;
tmp = scanf(" %c", &letter);
assert(tmp == 1);
TypeLetter(letter);
}
else if (cmd == 'U')
{
int number;
tmp = scanf("%d", &number);
assert(tmp == 1);
UndoCommands(number);
}
else if (cmd == 'P')
{
int index;
char letter;
tmp = scanf("%d", &index);
assert(tmp == 1);
letter = GetLetter(index);
printf("ans : %c\n", letter);
}
}
return 0;
}
#endif
