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

Автор do_good_, история, 8 лет назад, По-английски

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

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

»
8 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

Can you not use exclamation marks everywhere? It looks very rude.

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

first calculate prefix sums on each index

then start normal mo's algorithm,but in each step add or remove the prefix sum that you are on it

after that for each query you want to count the number of j's such that sum[i]-sum[j] = k,or you want to know the j's that sum[i]+k= sum[j],and you calculated this number before so you can easily answer each query