I got AC on Codeforces Round 905 (Div. 1) C. Minimum Array with my prewritten code sorting all arrays obtained (in lexicographic order) in $$$\mathcal{O}(n\log n + q\log q)$$$ time.
https://codeforces.net/contest/1887/submission/229244614
How is the processing time achieved? I made a tutorial (in Japanese) before. (https://www.mathenachia.blog/sortseqs/ and https://nachiavivias.github.io/cp-library/cpp/array/point-update-lex-sort.html) This time I make a brief explanation in English.
Problem
First you are given an array $$$(A _ 0[0],A _ 0[1],\ldots ,A _ 0[N-1])$$$ of length $$$N$$$ . You will construct other $$$Q$$$ arrays $$$A _ 1, A _ 2, \ldots , A _ Q$$$ as follows :
- For $$$k=1,2,\ldots ,Q$$$ (in order) , you are given integers $$$p _ k$$$ $$$(0 \leq p \leq N-1)$$$ and a value $$$x _ k$$$ . Overwrite $$$A _ i$$$ with the copy of $$$A _ {i-1}$$$ and change the value of $$$A _ {i}[p _ k]$$$ to $$$x _ k$$$ .
Find an array $$$(F _ 0,F _ 1,F _ 2,\ldots ,F _ Q)$$$ of nonnegative integers such that :
- $$$F _ i \lt F _ j \iff A _ i\lt A _ j$$$ (in lexicographic order) holds for $$$0 \leq i \leq Q$$$ , $$$0 \leq j \leq Q$$$ .
- Maximum value of $$$(F _ 0,F _ 1,F _ 2,\ldots ,F _ Q)$$$ is minimized.
In other words, sort all $$$Q+1$$$ arrays in lexicographic order.
Algorithm
Above I wrote like $$$A _ a[b]$$$ , so I call $$$a$$$ as array index and $$$b$$$ as time index .
Divide and Conquer array index . After we could sort every half, we can get full answer in linear time with radix sort (sort by second digit, then stable sort by first digit) .
When we divide array index, changing points are also divided in two groups. So we can compress time index . We can bound the sum of number of time index as $$$\mathcal{O}(n+q)$$$ in any layer of dividing. Of cource the number of the layers is $$$\mathcal{O}(\log n)$$$ . Therefore the time complexity is $$$\mathcal{O}((n+q) \log (n+q))$$$ overall ( the term $$$q\log q$$$ is for sorting given values ).
Main Usage
We can sometimes use this deterministic algorithm instead of randomized hash.
