Help in Mo's Algorithm Problem 877F

Правка en2, от do_good_, 2019-02-06 00:05:27

In Problem 877F , how to apply Mo's algorithm ? while traversing each block what to do ? editorial is not well explained ! __ Suppose a[] = { 1 , 1 , 1 , -1 } . We want to get all subarray's in the range 2--4 with sum = 1 .

Approach with HashMap would be linear complexity and total Time Complexity would be O(N*Q) if there are q queries ! **** how to reduce it to sqrt. decomposition ! Any idea ! __

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en7 Английский do_good_ 2019-02-06 09:17:46 4
en6 Английский do_good_ 2019-02-06 09:17:27 11 Tiny change: 'mposition ! Any idea ** ' -> 'mposition . ** '
en5 Английский do_good_ 2019-02-06 09:17:06 6
en4 Английский do_good_ 2019-02-06 06:55:12 12
en3 Английский do_good_ 2019-02-06 00:05:51 6
en2 Английский do_good_ 2019-02-06 00:05:27 14
en1 Английский do_good_ 2019-02-06 00:05:02 532 Initial revision (published)