Let's say that we have two choreographies. Let's see what information about them we have to keep, in order to know the value of their concatenation. Resulting value can be either the value of the first choreography, value of the second, or new alternating subsequence can be formed using some suffix of the first one, and prefix of the second choreography. Of course, we are only interested in the longest suffix and prefix. Also, the last letter in the first choreography must differ from the first letter in the second. So, for each choreography, we must store: value, length of the longest alternating suffix and prefix, and first and last letter. Note that we can also obtain all of this for the resulting choreography.

This leads to an efficient solution using a tournament (interval) tree. In each node of the tree, we store the information described above.

Task can also be solved using an existing set structure found in STL. We keep in the set all alternating subsequences. These subsequences are disjoint. Modifying a letter can lead either to splitting an existing interval, or to joining of the two intervals.

Both solutions have complexity ~\mathcal O(Q \log N)~.