Help in Mo's Algorithm Problem 877F

Revision en7, by do_good_, 2019-02-06 09:17:46

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 . **

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English do_good_ 2019-02-06 09:17:46 4
en6 English do_good_ 2019-02-06 09:17:27 11 Tiny change: 'mposition ! Any idea ** ' -> 'mposition . ** '
en5 English do_good_ 2019-02-06 09:17:06 6
en4 English do_good_ 2019-02-06 06:55:12 12
en3 English do_good_ 2019-02-06 00:05:51 6
en2 English do_good_ 2019-02-06 00:05:27 14
en1 English do_good_ 2019-02-06 00:05:02 532 Initial revision (published)