// chatGPT ?? no a good known of STL ... ;-}
#include <bits/stdc++.h>
using namespace std;
struct persistantTab {
int size = 1, countains = 0;
struct Node {
bool isLeaf;
char letter;
shared_ptr<Node> left;
shared_ptr<Node> right;
// Constructeur feuille
Node(char l = 0) : isLeaf(true), letter(l), left(nullptr), right(nullptr) {}
// Constructeur nœud interne
Node(shared_ptr<Node> lft, shared_ptr<Node> rgt)
: isLeaf(false), letter(0), left(lft), right(rgt) {}
// Copie
Node(const Node& other) : isLeaf(other.isLeaf), letter(other.letter),
left(other.left), right(other.right) {}
};
shared_ptr<Node> head = make_shared<Node>();
persistantTab() = default;
persistantTab(shared_ptr<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 = make_shared<Node>(head, nullptr);
newTab.size *= 2;
}
function<shared_ptr<Node>(shared_ptr<Node>, char, int, int, int)> addLIter =
[](shared_ptr<Node> node, char l, int pos, int low, int high) -> shared_ptr<Node> {
stack<tuple<shared_ptr<Node>, bool>> stk;
if (!node) node = make_shared<Node>();
shared_ptr<Node> current = node;
int clow = low, chigh = high;
while (chigh - clow > 1) {
int mid = (clow + chigh) / 2;
stk.emplace(current, pos >= mid);
if (!current->isLeaf) {
if (pos < mid) {
if (!current->left)
current->left = make_shared<Node>();
current = current->left;
chigh = mid;
} else {
if (!current->right)
current->right = make_shared<Node>();
current = current->right;
clow = mid;
}
} else {
// cas aberrant : transformer en nœud interne temporaire
current = make_shared<Node>();
chigh = mid;
}
}
shared_ptr<Node> updated = make_shared<Node>(l);
while (!stk.empty()) {
auto [parent, isRight] = stk.top();
stk.pop();
shared_ptr<Node> copy = make_shared<Node>(*parent);
if (!copy->isLeaf) {
if (isRight)
copy->right = updated;
else
copy->left = updated;
} else {
copy->isLeaf = false;
if (isRight) {
copy->left = nullptr;
copy->right = updated;
} else {
copy->left = updated;
copy->right = nullptr;
}
}
updated = copy;
}
return updated;
};
newTab.head = addLIter(newTab.head, L, newTab.countains - 1, 0, newTab.size);
return newTab;
}
char getLetter(int pos) const {
if (pos < 0 || pos >= countains)
return 0;
function<char(shared_ptr<Node>, int, int, int)> getLIter =
[](shared_ptr<Node> node, int p, int low, int high) -> char {
while (node) {
if (node->isLeaf && high - low == 1)
return node->letter;
if (!node->isLeaf) {
int mid = (low + high) / 2;
if (p < mid) {
node = node->left;
high = mid;
} else {
node = node->right;
low = mid;
}
} else {
return node->letter;
}
}
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
