Please help with Mos algo time complexity

Правка en2, от acash, 2024-09-25 06:23:49

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 ?

Теги sqrt_decomposition

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский acash 2024-09-25 06:23:49 11
en1 Английский acash 2024-09-25 06:23:33 715 Initial revision (published)