Mutate Array and Sort All Obtained Arrays in Lexicographic Order
Разница между en5 и en6, 0 символ(ов) изменены
I got AC on [Codeforces Round 905 (Div. 1) C. Minimum Array](https://codeforces.net/contest/1887/problem/C)↵
 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 _ 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 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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
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)