## TLE '17 Contest 7 P4 - Database

View as PDF

Points: 20 (partial)
Time limit: 2.0s
Python 4.0s
Memory limit: 512M

Author:
Problem type
Fax is about to enter his list into the Cronerian government database.

Fax McClad, Croneria's most skillful bounty hunter, has recently found a list filled with identification strings of various members of the Dankey Kang Gang!

There are strings on this list. Fax notices that the and string differ by at most character. The first string of this list will be denoted with .

Fax manually inputs all of the strings into a Cronerian government database, which sorts all of the strings by lexicographical order.

Now, Fax needs to make sure that he inputted the strings correctly. He will perform the following query times: what is the character of the string in the database?

Can you help Fax to determine what the expected output should be?

#### Constraints

All characters are lowercase characters in the English alphabet.

In each query, and .

115
215
350

#### Input Specification

The first line of input will contain , the first string of the list.

The next line of input will contain , the number of identification strings on the list.

lines of input follow. The line will contain an integer and a character . This denotes that string is obtained by changing the character of string to .

The next line of input will contain , the number of queries.

lines of input follow. Each line will be a query in the form i j.

#### Output Specification

Output on separate lines the answer to each query.

#### Sample Input

bbbbb
4
4 c
3 a
2 b
4
3 5
2 3
4 4
3 4

#### Sample Output

b
a
c
b

#### Explanation for Sample Output

The strings in the list are initially in the order bbbbb, bbbcb, bbacb, bbacb.

After putting all the strings into the database, their order is bbacb, bbacb, bbbbb, bbbcb.

• commented on April 4, 2018, 1:02 a.m.

Will there be an editorial for this question? :)

• commented on April 5, 2018, 12:30 a.m.

I'm not sure whether the author is planning to write an editorial but the author's intended solution is to maintain the hashes of the string with a persistent segment tree.

However, there exists a nice divide and conquer solution. Break into blocks of size where loops from to . For each block, we want to compute the relative order of the substring in this block among each of the versions of . We already have the relative order of the two halves of the block, so we can sort this and find the order of the entire block. It's important to not break ties in this solution (until the end). The time complexity of this is for each value of since over all the blocks (for a fixed ), there are at most distinct substrings. So the final time complexity is .

• commented on April 4, 2018, 9:06 a.m.

nope :P