Editorial for DMOPC '17 Contest 4 P6 - Best Girl
Submitting an official solution before solving the problem yourself is a bannable offence.
For the first subtask, greedily form prefixes of
MAKI. For each type ~2~ operation, loop through the letters and keep track of how many of each prefix can be formed (all at once).
Time Complexity: ~\mathcal O(QN)~
For the second subtask, consider greedily forming substrings of
MAKI. For example, if a
K is encountered and there is a
MA substring, then attach the
K to the
MA. If not, but there is an
A substring, then create the
AK substring. If neither of those exist, create the
K substring. The number of each substring which may be formed as subsequences over a substring of ~S~ can be represented as a ~4~ by ~4~ array. Now create a segment tree where each node of the segment tree is that ~4~ by ~4~ array for the node's substring of ~S~.
The main difficulty in this solution is merging the ~4~ by ~4~ arrays of two sections of ~S~. Consider the substrings of the left section of ~S~ by prioritizing the starting character of each substring and then prioritizing by length. For each of these substrings, a longer one can be created by using the characters of the right section of ~S~. Now when merging these substrings, it's important that the middle overlap is treated properly. In this case, the middle overlap should be treated as if this substring exists in a section between the left and right section. That is because there is a choice of whether to take the overlap from the left or the right.
Time Complexity: ~\mathcal O(Q\log N)~