The problem is as follows:
Given $k$ strings of size $n$, propose a data structure to support the following operations:
- Return the maximum of a string.
- Given an index $i$, and $2$ strings $a$ and $b$, create 2 strings to replace them: One of them is compised of the $i$ first elements of $a$ and $n-i$ of the last elements of $b$, and the other string is the $i$ first elements of $b$ followed by the $n-i$ last elements of $a$.
I suppose we need to do a preperation for the structure, and answer the queries as fast as possible.
One solution I thought of is as follows:
For each string, memoize the maximum in all prefixes and suffixes.
- Returning the maximum is trivial.
- Given the index $i$, the prefixes of the first half are still correct, and only the prefixes of the second half need to be recomputed, and only the first half's suffixes need to be recomputed.
But this results in $O(kn)$ preperation, $O(1)$ maximum, and $O(n)$ splits.
I also thought of using some sort of a Cartesian Tree or RMQ for this.
How can this be done more efficiently, possibly $O(1)$ in both queries?