Mutate Array and Sort All Obtained Arrays in Lexicographic Order

Revision en7, by Nachia, 2023-10-23 14:56:55

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.com/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 an integer $p _ k$ $( 0 \leq p _ k \leq N - 1 )$ and a value $x _ k$ . Overwrite $A _ k$ with the copy of $A _ {k-1}$ and change the value of $A _ {k}[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 time index and $b$ as array 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 entire process takes $\mathcal{O}((N+Q) \log (N+Q))$ time ( the term $Q\log Q$ is for sorting given values ).

Main Usage

We can sometimes use this deterministic algorithm instead of randomized hash.

History

Revisions

Rev. Lang. By When Δ Comment
en7 Nachia 2023-10-23 14:56:55 527 accrate text and add supplement based on comments
en6 Nachia 2023-10-22 19:58:11 0 (published)
en5 Nachia 2023-10-22 19:52:01 4 Tiny change: '+Q) \log (n+q))$overal' -> '+Q) \log (N+Q))$ overal'
en4 Nachia 2023-10-22 19:51:47 14
en3 Nachia 2023-10-22 19:47:15 6
en2 Nachia 2023-10-22 19:37:11 18
en1 Nachia 2023-10-22 19:36:30 2135 Initial revision (saved to drafts)