Mutate Array and Sort All Obtained Arrays in Lexicographic Order
Difference between en6 and en7, changed 527 character(s)
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 
an integers $p _ k$  $( 0 \leq p _ k \leq N-1 - 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 
entimrcomplexity iprocess takes $\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 randomize
time ( the term $Q\log Q$ is for sorting given values ).↵

## Main Usage↵

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

## Supplement Based on Comments↵

Thank you for your helpful comments.↵

* You can search [Merkle tree](https://en.wikipedia.org/wiki/Merkle_tree) for a broader perspective on this topic.↵
* Baekjoon Online Judge already has a [judge for a similar problem](https://www.acmicpc.net/problem/15930) at least as har
hash this example.

History

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