### PROBLEM LINK:

**Author:** Satyam Shubham

**Tester:** Alexey Zayakin

**Editorialist:** Oleksandr Kulkov

### DIFFICULTY:

MEDIUM-HARD

### PREREQUISITES:

Suffix tree

### PROBLEM:

You’re given string s. String t is obtained by concatenating all of s substrings in lexicographical order. You have to answer queries of finding k^{th} letter in t in online.

### QUICK EXPLANATION

For each vertex of suffix tree calculate how much letters will it take to write down all substrings up to the one ending in this vertex. Use binary search over these values to find substring from which k^{th} letter is taken.

### EXPLANATION:

When it comes to substrings it’s only natural to use some suffix structure, namely suffix tree. Let’s recall how to get all substrings of s in lexicographical order given suffix tree of s. If it is not compressed then you can just walk over all its vertices in lexicographical order and the next substring will be the one corresponding to path from the root to the current vertex.

Now consider compressed suffix tree. Let’s sort all vertices of the tree in lexicographical order and calculate for each explicit vertex v how many letters we will obtain if we concatenate all substrings up to the one corresponding to this vertex and denote it by cnt_v. Obviously, cnt_{root}=0. Now denote explicit parent of vertex v by par_v, vertex previous in lexicographical order to v by pre_v and length of substring corresponding to vertex v by len_v, then

After we calculated this, we are ready to answer queries. If we have number k in the query, we should find such vertex v that

That will mean that substring which holds k^{th} letter is on the edge between par_v and v. Now we can find particular length of such substring. It will be equal to m such that

We know where can we find any occurence of strings from edge in s and we know length of particular string. Now only thing left to do for us is to output letter number \left(k-cnt_{pre_v}-\sum\limits_{i=len_{par_v}+1}^{m-1} i\right) of this string.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.