I got AC on [Codeforces Round 905 (Div. 1) C. Minimum Array](https://mirror.codeforces.com/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://mirror.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 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 entimre complexity 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 randomizetime ( 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 hardhash this example.
with my prewritten code sorting all arrays obtained (in lexicographic order) in $\mathcal{O}(n\log n + q\log q)$ time.↵
↵
https://mirror.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
↵
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 enti
↵
## Main Usage↵
↵
We can sometimes use this deterministic algorithm instead of randomize
↵
## 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 hard
