Hello Codeforces,

Recently I was solving some problems and came across IOI 2012, Crayfish Scrivener. It is quite an interesting problem. I think my solution for 100 points is pretty cool so I decided to post it here. Hopefully it has not been mentioned before :)

For this solution we will be using 1-based indexing.

Firstly, I noticed that actually adding characters to the end of the string seems a little annoying to optimize. So I tried converting it to a more static problem. First we must notice that this dynamic string can be represented using a static char array. Also notice that for all subtasks, the number of queries is at most $$$1,000,000$$$ ($$$10^6$$$). Thus, the maximum size of our string is $$$10^6$$$. So if we have a char array of size $$$10^6$$$, initialized to some default value, and keep track of the actual "size" of the represented string in an integer, in order to "type a letter", we can just update the index ($$$size + 1$$$) with the desired letter (this is a point update) without affecting the correctness of our algorithm.

Actually, this reduction allows us to reframe the problem in a way that is very intuitive to solve. Observe that the $$$Undo$$$ operation just requires us to "copy" some arbitrary previous revision of the char array, and make a new revision from it. The $$$TypeLetter$$$ operation just requires us to do a make a new revision that does a point update on the current revision. The $$$GetLetter$$$ operation just requires us to get the value at a specified index, which is a point query. So we need a persistent data structure (to access any previous revision quickly) which can also do point updates and point queries quickly.

What data structure supports all this? Persistent segment trees! Thus, the solution is to build a persistent segment tree on the aforementioned char array.

Its space complexity is $$$O(QlogN)$$$ where $$$Q$$$ is the number of queries and $$$N$$$ is the size of our char array ($$$10^6$$$ in this case, the number of queries) which is $$$O(QlogQ)$$$. "Copying" a previous revision $$$O(1)$$$. Point updates and point queries are $$$O(logN)$$$, which is $$$O(logQ)$$$. Our final time complexity is $$$O(QlogQ)$$$. This is good enough to score 100 points.

Note: We do not use the full power of segment tree for this problem as all the char information is stored in the leaf nodes, which represent a single index.

Implementation note: Don't forget to convert 0-based indexing given in input to 1-based indexing, or implement your solution in 0-based indexing (idea stays the same, just a few minor changes).

PS: I hope you enjoyed reading through my first Codeforces blog. I spent a lot of time on it and if you have any suggestions or tips for improvement please post them in the comments. Though maybe this is not the most elegant way to solve the problem, this is the first idea I came up with and I feel like I understand it a lot more than the other solution which uses binary jumping (though I think it is pretty cool as well, you can view it here).

//1-based indexing for everything
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1000005; //just an arbitrarily high limit 
struct Segtree{
    int vcnt, root[MAX_N], rootCnt;
    char f[MAX_N * 22];
    int lc[MAX_N * 22], rc[MAX_N * 22];
    void createNode(int &x){ x = ++vcnt; }
    void build(int &x, int l, int r){
        if(x == 0) createNode(x);
        if(l == r){
            f[x] = 0;
            return;
        }
        int mid = (l + r) / 2;
        build(lc[x], l, mid);
        build(rc[x], mid + 1, r);
    }
    void update(int &x, int l, int r, int oldX, int pos, int val){
        if(x == 0) createNode(x);
        if(l == r){
            f[x] = val; //Set leaf node to new value
            return;
        }
        int mid = (l + r) / 2;
        if(pos <= mid){
            update(lc[x], l, mid, lc[oldX], pos, val);
            rc[x] = rc[oldX];
        } else {
            update(rc[x], mid + 1, r, rc[oldX], pos, val);
            lc[x] = lc[oldX];
        }
    }
    char query(int x, int l, int r, int q){
        if(x == 0) return 0;
        if(l == r) return f[x];
        int mid = (l + r) / 2;
        if(q <= mid) return query(lc[x], l, mid, q); else return query(rc[x], mid+1, r, q);
    }
};
int chs[MAX_N]; //count of chars in i'th revision, also index of last char because of 1-based indexing
Segtree T;
int sz = 1000001; //size of our "char array"
void Init() {
    T.build(T.root[++T.rootCnt], 1ll, sz);
}
void TypeLetter(char x) {
    T.rootCnt++;
    T.update(T.root[T.rootCnt], 1, sz, T.root[T.rootCnt-1], chs[T.rootCnt-1]+1, x);
    chs[T.rootCnt] = chs[T.rootCnt-1] + 1;
}
void UndoCommands(signed g) {
    T.rootCnt++;
    T.root[T.rootCnt] = T.root[T.rootCnt-g-1];
    chs[T.rootCnt] = chs[T.rootCnt-g-1];
} 
char GetLetter(signed p) {
    return T.query(T.root[T.rootCnt], 1, sz, p+1);
}