This is a topic of complexity analysis (for Round 975 Div. 1 E) with no special algorithm.

Problem

An integer sequense $$$(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\geq 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)$$$ .

A = [0] * (n+2)
A[0] = n+1
A[n+1] = 0

def f(k) :
    # find a_k

def search(l, r) :
    if A[l-1] == A[r] :
        return
    if l >= r
        return
    m = (l + r) // 2
    A[m] = f(m)
    search(l, m-1)
    search(m+1, r)

Complexity Analysis

I saw this algorithm in physics0523's blog post (https://physics0523.hatenablog.com/entry/2023/10/11/155814) and I suggested the conplexity be probably $$$O(\sqrt{n})$$$ . Finally noshi91 made a proof(Twitter link) which says that is.

It is like following:

Only $$$O(2^{d/2})$$$ calls in depth $$$d$$$ .

Since the algorithm is just an binary search, searching space $$$0,1,2,\ldots ,n,n+1$$$ is splitted in $$$2^d$$$ segments with almost same sizes before it reaches depth $$$d$$$ . Especially the first one is $$$0,1,2,\ldots ,\lfloor (n+1)/2^d \rfloor$$$ .

Suppose $$$d$$$ even. The group of segments without the first $$$2^{d/2}$$$ segments bound $$$\lfloor (n+1)/2^{d/2} \rfloor +1,\ldots ,n$$$ . For $$$n/2^{d/2}\leq x\leq n$$$ we have $$$a _ x\leq 2^{d/2}$$$ so we need to search only $$$2\times 2^{d/2}$$$ segments in depth $$$d+1$$$ .

For the case with odd $$$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})$$$ .

One Additional Argument

We can process Decremental Predecessor Query Problem in amortized $$$O(1)$$$ time per query. For Round 975 Div. 1 E , we can use that instad of a general DSU to solve the entire task in $$$O(n\sqrt{n})$$$ time. Submission 283309295