#include<iostream> #include<cmath> #include<vector> using namespace std; char T[1000001]; int dad[1000001], dadH[1000001], H[1000001]; vector<int> v; int act, it; void Init() { it = 1; act = 0; H[0] = -1; dad[0] = dadH[0] = 0; v.clear(); } void TypeLetter(char L) { T[it] = L; H[it] = H[act]+1; dad[it] = act; if(H[it] % 1000 == 0) //sqrt(1000000) => 1000 dadH[it] = it; else dadH[it] = dadH[act]; v.push_back(it); act = it++; } void UndoCommands(int U) { act = v[v.size() - U - 1]; v.push_back(act); } char GetLetter(int P) { // O(sqrt(height)) int i = act; while(H[ dadH[i] ] > P) i = dadH[i];// O(sqrt(height)) while(H[ dad[i] ] >= P) i = dad[i]; // O(sqrt(height)) return T[i]; } // int main() { // int t; // cin >> t; // Init(); // for (int i = 0; i < t; i++) { // char c, d; int e; // cin >> c; // switch (c) { // case 'T': // cin >> d; // TypeLetter(d); // break; // case 'P': // cin >> e; // cout << GetLetter(e) << '\n'; // break; // default: // cin >> e; // UndoCommands(e); // } // } // }