This is a topic on complexity analysis (for Round 975 Div. 1 E) with no special algorithm.
Problem
An integer sequence (a1,a2,…,an) is hidden. We know:
- It is non-increasing. ( ak≥ak+1 )
- 0≤ak≤n/k
Suppose we can get one value of ak in O(C) time. Find all values of a1,a2,…,an .
Algorithm
Put a0=n+1 and an+1=0 and call SEARCH(1,n) . In a call of SEARCH(l,r) , do nothing if l>r . Also no more search is required if al−1=ar+1 . Otherwise evaluate a⌊(l+r)/2⌋ and recursively call SEARCH(l,⌊(l+r)/2⌋−1) and SEARCH(⌊(l+r)/2⌋+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(n+√nC) . Finally noshi91 made a proof(Twitter link) which says that is.
Only O(2d/2) calls in depth d .
Since the algorithm is just a binary search, searching space [0,n+1) is splitted in 2d segments with almost same sizes before it reaches depth d . Especially the first one is [0,⌊(n+1)/2d⌋) .
Suppose d is odd and set d′=d−1 . In depth d′ , the group of segments without the first 2d′/2 segments bounds [⌊(n+1)/2d′/2⌋,n+1) . For n/2d′/2≤x≤n we have ax≤2d′/2 so we need to search only 3×2d′/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 ⌈log2n⌉∑d=02d/2 is bounded as O(√n) , the processing time overall is O(n+√nC) .
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√n) time. Submission 283309295
Auto comment: topic has been updated by Nachia (previous revision, new revision, compare).
Sample problem for this technique: 1039D - You Are Given a Tree
O(√n) is a little bit confusing, probably you can change it into "assume that we can get a value of a in f(n) time, then we can get all a in O(n+f(n)√n)"?
Thanks! I prefer C to f(n) , I think it's clear enough.