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

Please help with Mos algo time complexity

Автор acash, история, 3 месяца назад, По-английски

Hi everyone I was reading article on mos algo from Mos algo. Let's say we have 1e5 and the queries are like (b1,bn) (b2,b3) (b4,bn) (b5,b6) (b7,bn). If we sort the queries according to Mos algorithm where bi represents the block number it seems that the left pointer will always be increasing However the right pointer is jumping between blocks (eg bn to b3, b3 to bn and bn to b6) Wouldnt the right pointer need O(n) time because if we want to go from bi to bn then we have traverse all the elements in all the blocks present between bi to bn Please help what i am getting wrong here ?

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

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

Auto comment: topic has been updated by acash (previous revision, new revision, compare).

→ Ответить
»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

figure it out yourself this is why you are gray lol

→ Ответить
»
3 месяца назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Read the rev.1 of this comment if you don't understand the Mo's algorithm complexity.

In your example the additional $$$O(n)$$$ is given by switching block, not per query. And because your $$$q$$$ is too small, it's possible switch a block every query. However you only need to switch block for at most $$$O(\dfrac{n}{B})$$$ times no matter how much queries there are. It's impossible to construct more than $$$O(\dfrac{n}{B})$$$ queries in which the right pointer of each query belongs to a different block.

→ Ответить
  • »
    »
    3 месяца назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks for the reply Sir, It seems i got it. Since there are B blocks in total of B size. For each block we can have this jump of O(n) time, which will gives us n * B which is nsqrt(n) and also for left pointer which is only increasing it we will get overall O(n). So total O(n) + O(nsqrt(n))

    → Ответить