TLE '17 Contest 7 P4 - Database

View as PDF

Submit solution

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

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 N strings on this list. Fax notices that the i^\text{th} and (i+1)^\text{th} string differ by at most 1 character. The first string of this list will be denoted with S.

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 Q times: what is the j^\text{th} character of the i^\text{th} string in the database?

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


1 \le N,Q,|S| \le 2 \times 10^5

All characters are lowercase characters in the English alphabet.

1 \le x \le |S|

In each query, 1 \le i \le N and 1 \le j \le |S|.

SubtaskPointsAdditional constraints
1151 \le |S| \le 20
2151 \le N,Q,|S| \le 500
3501 \le N,Q,|S| \le 10^5
420No additional constraints.

Input Specification

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

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

N-1 lines of input follow. The k^\text{th} line will contain an integer x and a character c. This denotes that string k+1 is obtained by changing the x^\text{th} character of string k to c.

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

Q 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

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

Sample Output


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.


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

    Will there be an editorial for this question? :)

    • 12
      r3mark  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 S into blocks of size 2^i where i loops from 1 to \log_2{|S|}. For each block, we want to compute the relative order of the substring in this block among each of the N versions of S. 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 O(N\log N) for each value of i since over all the blocks (for a fixed i), there are at most N distinct substrings. So the final time complexity is O(N\log N \log |S|+Q).

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

      nope :P