do_good_'s blog

Help in Mo's Algorithm Problem 877F
By do_good_, history, 6 years ago, In English

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

  • Vote: I like it
  • -8
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

            → Reply