ligaydima's blog

3d Mo algorithm
By ligaydima, history, 5 years ago, translation, In English

Where can I find some theory on 3d Mo's algorithm(like Mo's algorithm, but with updates)?

  • Vote: I like it
  • +7
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been translated by ligaydima (original revision, translated revision, compare)

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Take a look at this problem and its editorial: https://codeforces.net/contest/940/problem/F

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Actual Discussion: https://codeforces.net/blog/entry/44711

Tl;dr version that I understood.

Online Mo's Algorithm : $$$O((N + Q)*N^{\frac{2}{3}})$$$

Method:

Group into contiguous buckets, each of size $$$N^{\frac{2}{3}}$$$.

So number of buckets = $$$N^{\frac{1}{3}}$$$

for lbucket = 0 to N^1/3:
    for rbucket = lbucket to N^1/3:
        // iterate over the stream of all the updates AND queries from this pair
        // i.e the L belongs to [lbucket * N^2/3, (lbucket + 1) * N^2/3)
        // and R belongs to [rbucket * N^2/3, (rbucket + 1) * N^2/3)
        // in chronological order
            if at a query: 
                slide l pointer to query l, slide r pointer to query r. 
                // should be 2*N^2/3 shifts at most
                print global answer
            if at an update:
                update the global state
→ Reply