Блог пользователя ligaydima

Автор ligaydima, история, 5 лет назад, По-русски

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

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Actual Discussion: https://codeforces.me/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