This is a topic on complexity analysis (for [Round 975 Div. 1 E](https://mirror.codeforces.com/contest/2018/problem/E2)) with no special algorithm.↵
↵
## Problem↵
↵
An integer sequence $(a _ 1,a _ 2,\ldots ,a _ n)$ is hidden. We know:↵
↵
* It is non-increasing. ( $a _ k\geq a _ {k+1}$ )↵
* $0\leq a _ k\leq n/k$↵
↵
Suppose we can get one value of $a _ k$ in $O(1)$ time. Find all values of $a _ 1,a _ 2,\ldots ,a _ n$ .↵
↵
## Algorithm↵
↵
Put $a _ 0=n+1$ and $a _ {n+1}=0$ and call $\text{S} _ \text{EARCH}(1,n)$ . In a call of $\text{S} _ \text{EARCH}(l,r)$ , do nothing if $l\gt r$ . Also no more search is required if $a _ {l-1}=a _ {r+1}$ . Otherwise evaluate $a _ {\lfloor (l+r)/2\rfloor}$ and recursively call $\text{S} _ \text{EARCH}(l,\lfloor (l+r)/2\rfloor -1)$ and $\text{S} _ \text{EARCH}(\lfloor (l+r)/2\rfloor +1,r)$ .↵
↵
```py↵
A = [0] * (n+2)↵
A[0] = n+1↵
A[n+1] = 0↵
↵
def f(k) :↵
# find a_k↵
↵
def search(l, r) :↵
if l >= r↵
return↵
if A[l-1] == A[r+1] :↵
for x in range(l, r+1) :↵
A[x] = A[l-1]↵
return↵
m = (l + r) // 2↵
A[m] = f(m)↵
search(l, m-1)↵
search(m+1, r)↵
```↵
↵
## Complexity Analysis↵
↵
I saw this algorithm in [user:physics0523,2024-09-28]'s blog post (https://physics0523.hatenablog.com/entry/2023/10/11/155814) and I suggested the complexity be probably $O(\sqrt{n})$ . Finally [user:noshi91,2024-09-28] made a proof([Twitter link](https://x.com/noshi91/status/1752944251082797370)) which says that is.↵
↵
### Only $O(2^{d/2})$ calls in depth $d$ .↵
↵
Since the algorithm is just a binary search, searching space $[0,n+1)$ is splitted in $2^d$ segments with almost same sizes before it reaches depth $d$ . Especially the first one is $[0,\lfloor (n+1)/2^d \rfloor)$ .↵
↵
Suppose $d$ iseven. Todd and set $d'=d-1$ . In depth $d'$ , the group of segments without the first $2^{d'/2}$ segments bounds $[\lfloor (n+1)/2^{d'/2} \rfloor ,n+1)$ . For $n/2^{d'/2}\leq x\leq n$ we have $a _ x\leq 2^{d'/2}$ so we need to search only $23\times 2^{d'/2}+1$ segments in depth $d+1$ .↵
↵
For the case withoddeven $d$ , it is obvious that we have no more calls than twice as depth-$(d-1)$ calls.↵
↵
---↵
↵
Since $\displaystyle \sum _ {d=0} ^ {\lceil \log _ 2 n \rceil} 2^{d/2} $ is bounded as $O(\sqrt{n})$ , the processing time overall is $O(\sqrt{n})$ .↵
↵
## Bonus↵
↵
We can process the Decremental Predecessor Query Problem in amortized $O(1)$ time per query. For [Round 975 Div. 1 E](https://mirror.codeforces.com/contest/2018/problem/E2) , we can use that instead of a general DSU to solve the entire task in $O(n\sqrt{n})$ time. [Submission 283309295](https://mirror.codeforces.com/contest/2018/submission/283309295)↵
↵
## Problem↵
↵
An integer sequence $(a _ 1,a _ 2,\ldots ,a _ n)$ is hidden. We know:↵
↵
* It is non-increasing. ( $a _ k\geq a _ {k+1}$ )↵
* $0\leq a _ k\leq n/k$↵
↵
Suppose we can get one value of $a _ k$ in $O(1)$ time. Find all values of $a _ 1,a _ 2,\ldots ,a _ n$ .↵
↵
## Algorithm↵
↵
Put $a _ 0=n+1$ and $a _ {n+1}=0$ and call $\text{S} _ \text{EARCH}(1,n)$ . In a call of $\text{S} _ \text{EARCH}(l,r)$ , do nothing if $l\gt r$ . Also no more search is required if $a _ {l-1}=a _ {r+1}$ . Otherwise evaluate $a _ {\lfloor (l+r)/2\rfloor}$ and recursively call $\text{S} _ \text{EARCH}(l,\lfloor (l+r)/2\rfloor -1)$ and $\text{S} _ \text{EARCH}(\lfloor (l+r)/2\rfloor +1,r)$ .↵
↵
```py↵
A = [0] * (n+2)↵
A[0] = n+1↵
A[n+1] = 0↵
↵
def f(k) :↵
# find a_k↵
↵
def search(l, r) :↵
if l >= r↵
return↵
if A[l-1] == A[r+1] :↵
for x in range(l, r+1) :↵
A[x] = A[l-1]↵
return↵
m = (l + r) // 2↵
A[m] = f(m)↵
search(l, m-1)↵
search(m+1, r)↵
```↵
↵
## Complexity Analysis↵
↵
I saw this algorithm in [user:physics0523,2024-09-28]'s blog post (https://physics0523.hatenablog.com/entry/2023/10/11/155814) and I suggested the complexity be probably $O(\sqrt{n})$ . Finally [user:noshi91,2024-09-28] made a proof([Twitter link](https://x.com/noshi91/status/1752944251082797370)) which says that is.↵
↵
### Only $O(2^{d/2})$ calls in depth $d$ .↵
↵
Since the algorithm is just a binary search, searching space $[0,n+1)$ is splitted in $2^d$ segments with almost same sizes before it reaches depth $d$ . Especially the first one is $[0,\lfloor (n+1)/2^d \rfloor)$ .↵
↵
Suppose $d$ is
↵
For the case with
↵
---↵
↵
Since $\displaystyle \sum _ {d=0} ^ {\lceil \log _ 2 n \rceil} 2^{d/2} $ is bounded as $O(\sqrt{n})$ , the processing time overall is $O(\sqrt{n})$ .↵
↵
## Bonus↵
↵
We can process the Decremental Predecessor Query Problem in amortized $O(1)$ time per query. For [Round 975 Div. 1 E](https://mirror.codeforces.com/contest/2018/problem/E2) , we can use that instead of a general DSU to solve the entire task in $O(n\sqrt{n})$ time. [Submission 283309295](https://mirror.codeforces.com/contest/2018/submission/283309295)↵
