This is a topic on complexity analysis (for Round 975 Div. 1 E) 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)$$$ .

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 physics0523's blog post (https://physics0523.hatenablog.com/entry/2023/10/11/155814) and I suggested the complexity be probably $$$O(\sqrt{n})$$$ . Finally noshi91 made a proof(Twitter link) 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 even. 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 $$$2\times 2^{d/2}+1$$$ 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})$$$ .

Bonus

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