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 odd 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 $$$3\times 2^{d'/2}+1$$$ segments in depth $$$d$$$ .
For the case with even $$$d$$$ , 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
