/*
Eyoo it's a persistent dynamic array!! :D
For the version history, all I need to do is to
maintain a dynamic array, and then
the undo command is just appending the previous
state to the array
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
// For the dynamic array, I will use an INFINITE array
class Array {
private:
char _v;
Array* _odd;
Array* _even;
public:
Array(char a_v, Array* a_odd, Array* a_even): _v(a_v), _odd(a_odd), _even(a_even) {};
char v() {
return _v;
}
Array* odd() {
if(_odd == nullptr) _odd = new Array(' ', nullptr, nullptr);
return _odd;
}
Array* even() {
if(_even == nullptr) _even = new Array(' ', nullptr, nullptr);
return _even;
}
char get(int i) {
if(i == 0) return _v;
else if(i & 1) return odd()->get((i - 1) >> 1);
else return even()->get((i - 1) >> 1);
}
Array* set(int i, char c) {
if(i == 0) return new Array(c, _odd, _even);
else if(i & 1) return new Array(_v, odd()->set((i - 1) >> 1, c), _even);
else return new Array(_v, _odd, even()->set((i - 1) >> 1, c));
}
};
class VersionedArray {
private:
vector<int> _sizes;
vector<Array*> _stack;
public:
VersionedArray() {};
inline void push_version(Array* v) {
_stack.push_back(v);
}
inline void push_size(int size) {
_sizes.push_back(size);
}
inline int num_versions() {
return _stack.size();
}
inline Array* get_version(int i) {
return _stack[i];
}
inline Array* get_past_version(int i) {
return get_version(num_versions() - i - 1);
}
inline Array* top() {
return _stack[num_versions() - 1];
}
inline int get_past_size(int i) {
return _sizes[num_versions() - i - 1];
}
inline int top_size() {
return _sizes[num_versions() - 1];
}
static VersionedArray create() {
Array* first = new Array(' ', nullptr, nullptr);
VersionedArray instance;
instance.push_version(first);
instance.push_size(0);
return instance;
}
};
VersionedArray versions;
void Init() {
versions = VersionedArray::create();
}
void TypeLetter(char L) {
int prev_top_size = versions.top_size();
versions.push_size(prev_top_size + 1);
versions.push_version(versions.top()->set(prev_top_size, L));
}
void UndoCommands(int U) {
versions.push_size(versions.get_past_size(U));
versions.push_version(versions.get_past_version(U));
}
char GetLetter(int P) {
return versions.top()->get(P);
}
