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

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

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
  • Проголосовать: не нравится

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

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

»
6 лет назад, # |
  Проголосовать: нравится 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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    what is normal mo's algorithm , this is where i am having difficulty . since the problem can be solved using n*q time , by every time querying number of subaarryas with sum = k in the range L , R by the using prefix sum and hashmap.

    but from here how should i reduce it to sqrt(N) , how to apply mo's algo. here , what to do ?

    M_H_H_7

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      https://blog.anudeep2011.com/mos-algorithm/ Here you can learn about normal Mo's Algorithm.

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        But doesn't this blog is very specific , that is the algo have been applied only for the problem : count all elements whose count >=3.

        how to deal with other problems .

        doped.silicon

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          is mo's algorithm is just sorting the queries ? As Audeep mentioned that __ We are done with MO’s algorithm, it is just an ordering.

          • »
            »
            »
            »
            »
            »
            6 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            MO's Algorithm is just a smart way to process the offline queries in a certain order which reduces the overall complexity of the problem to O(Sqrt(N) * N). If we don't sort the queries and solve the problem the complexity will remain O(N^2).