# IOI 2012 – Crayfish Scrivener

Problem description: Crayfish Scrivener

The first thing that we need is save the TEXT and know how it can be undo. This is easy we need a tree when it do undo only jump for the actions saved, for do TypeLetter add the new letter in the tree (see image). With this tree we can obtain the i-th character in the text, we always point to the last character and climb in the tree.

Ok it can solve task-4 but we need solve task-5 (The total number of commands and queries is between 1 and 1.000.000), our problem is ‘GetLetter’ function, it is O(P) for now. In the worst case the P can be 500.000 and it can be called 500.000 times.

A good improvement is for do ‘GetLetter’ in O( sqrt(height of the tree) ). It need save the dad of the node and the ‘sqrt(height of the tree)’-th dad of each node. When the search is for a ‘P’ upper to ‘sqrt(height of the tree)’ we can jump ‘sqrt(height of the tree)’ nodes. Now ‘GetLetter’ function is O(sqrt(height of the tree) )

This is my implementation

```#include<iostream>
#include<cmath>
#include<vector>
using namespace std;

char T;
vector<int> v;
int act, it;

void Init() {
it = 1;
act = 0;
H = -1;
v.clear();
}

void TypeLetter(char L) {
T[it] = L;
H[it] = H[act]+1;
if(H[it] % 1000 == 0) //sqrt(1000000) => 1000
else
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;
return T[i];
}

int main(){
Init();
TypeLetter('a');			//  a
TypeLetter('b');			//  ab
cout<<GetLetter(1)<<endl;	//b ab
TypeLetter('d');			//  abd
UndoCommands(2);			//  a
UndoCommands(1);			//  abd
cout<<GetLetter(2)<<endl;	//d abd
TypeLetter('e');			//  abde
UndoCommands(1);			//  abd
UndoCommands(5);			//  ab
TypeLetter('c');			//  abc
cout<<GetLetter(2)<<endl;	//c abc
UndoCommands(2);			//  abd
cout<<GetLetter(2)<<endl;	//d abd
}```