Square Root Decomposition or Mo's Algorithm

MO’s algorithm is just an order in which we process the queries. We were given M queries, we will re-order the queries in a particular order and then process them. Clearly, this is an offline algorithm. Each query has L and R, we will call them opening and closing. Let us divide the given input array into Sqrt(N) blocks (virtually) . Each block will be N / Sqrt(N) = Sqrt(N) size. Each opening has to fall in one of these blocks. Each closing has to fall in one of these blocks.
How does the final order look like?
All the queries are first ordered in ascending order of their block number (block number is the block in which its opening falls). Ties are ordered in ascending order of their R value.
For example consider following queries and assume we have 3 blocks each of size 3.
{0, 3} {1, 7} {2, 8} {7, 8} {4, 8} {4, 4} {1, 2}
Let us re-order them based on their block number. (L/Block_size)
{0, 3} {1, 7} {2, 8} {1, 2} {4, 8} {4, 4} {7, 8}
Now let us re-order ties based on their R value.
{1, 2} {0, 3} {1, 7} {2, 8} {4, 4} {4, 8} {7, 8}
Complexity of above algorithm – O(Sqrt(N) * N)
Notes:
  • we cannot use this algorithm when we are forced to stick to given order of queries. 
  • we cannot use this when there are update operations.

Operations(Templates):-


Compare:
bool cmp(node x, node y) {
 if(x.L/BLOCK != y.L/BLOCK) {
  // different blocks, so sort by block.
  return x.L/BLOCK < y.L/BLOCK;
 }
 // same block, so sort by R value
 return x.R < y.R;
}



Conditions:
for each query:
  // currentL should go to L, currentR should go to R

  while currentL &amp;lt; L:
    remove(currentL)
    currentL++

 while currentR &amp;lt; R:
    add(currentR)
    currentR++

  while currentL &amp;gt; L:
    add(currentL)
    currentL--

  while currentR &amp;gt; R:
    remove(currentR)
    currentR--

  output answer


Doubts?

Reference Links:

Lets Jump to some questions :

Question 1:

Given an array of N integers and Q queries each of which asks to find the sum of all numbers Ai, for those Ai which has an odd frequency in subarray L to R

Input Output

5 1
1 2 2 2 1 7
3 6
1 3
1 4
1 5

Solution: 
#include <bits/stdc++.h>
using namespace std;

#define N 200005
#define A 200005
int BLOCK;

int cnt[A]={0}, a[N];
long long int sum=0, ans[N];

struct node {
 int L, R, i;
}q[N];

bool cmp(node x, node y) {
 if(x.L/BLOCK != y.L/BLOCK) {
  // different blocks, so sort by block.
  return x.L/BLOCK < y.L/BLOCK;
 }
 // same block, so sort by R value
 return x.R < y.R;
}

void add(int position) {
 cnt[a[position]]++;
 if(cnt[a[position]] %2 == 1) {
  sum+=(a[position]*cnt[a[position]]);
 }
 else{
  if(cnt[a[position]]>=0)
  sum-=(a[position]*max(1,(cnt[a[position]]-1)));
 }
}

void remove(int position) {
 cnt[a[position]]--;
 if(cnt[a[position]]%2 ==1) {
  sum+=(a[position]*cnt[a[position]]);
 }
 else{
  if(cnt[a[position]]>=0)
  sum-=(a[position]*max(1,(cnt[a[position]]-1)));
 }
}

int main() {
 int n;
 scanf("%d", &n);
 BLOCK = sqrt(n);
 for(int i=0; i<n; i++)
  scanf("%d", &a[i]);

 int m;
 scanf("%d", &m);
 for(int i=0; i<m; i++) {
  scanf("%d%d", &q[i].L, &q[i].R);
  q[i].L--; q[i].R--;
  q[i].i = i;
 }

 sort(q, q + m, cmp);

 int currentL = 0, currentR = 0;
 for(int i=0; i<m; i++) {
  
  int L = q[i].L, R = q[i].R;
  //cout<<L<<" "<<R<<endl;
  while(currentL > L) {
   add(currentL-1);
   currentL--;
   //cout<<sum<<" ";
  }
  while(currentR <= R) {
   add(currentR);
   currentR++;
   //cout<<sum<<" ";
  }
  while(currentL < L) {
   remove(currentL);
   currentL++;
   //cout<<sum<<" ";
  }
  
  while(currentR > R+1) {
   remove(currentR-1);
   currentR--;
   //cout<<sum<<" ";
  }
  ans[q[i].i] = sum;
  //cout<<endl;
 }

 for(int i=0; i<m; i++)
  printf("%lld\n", ans[i]);
}



Question 2: Link To Question
N strings numbered 1 to N. The number of times the string S appears in the range [l,r]
 Input                       Output
3                     1
abc                   2
def                   0
abc
3
1 2 abc
1 3 abc
1 2 hgj


Solution:


#include <bits/stdc++.h>
using namespace std;

#define N 100005
#define A 100005
int BLOCK;

vector <string> a(N);
unordered_map<string,int> mymap;
int sum=0, ans[N];

struct node {
 int L, R, i;
 string s;
}q[N];

bool cmp(node x, node y) {
 if(x.L/BLOCK != y.L/BLOCK) {
  // different blocks, so sort by block.
  return x.L/BLOCK < y.L/BLOCK;
 }
 // same block, so sort by R value
 return x.R < y.R;
}

void add(int position) {
    mymap[a[position]]+=1;
}

void remove(int position) {
  mymap[a[position]]-=1;
}

int main() {
 int n;
 scanf("%d", &n);
 BLOCK = sqrt(n);
 for(int i=0; i<n; i++)
 {
     string s1;
     cin>>a[i];
     //cout<<s1<<endl;
     //a.push_back(s1);
 }

 int m;
 scanf("%d", &m);
 for(int i=0; i<m; i++) {
  cin>>q[i].L>>q[i].R>>q[i].s;
  q[i].L--; q[i].R--;
  q[i].i = i;
 }

 sort(q, q + m, cmp);

 int currentL = 0, currentR = 0;
 for(int i=0; i<m; i++) {
  
  int L = q[i].L, R = q[i].R;
  string S=q[i].s;
  //cout<<L<<" "<<R<<endl;
  while(currentL < L) {
   remove(currentL);
   currentL++;
   //cout<<sum<<" ";
  }
  while(currentL > L) {
   add(currentL-1);
   currentL--;
   //cout<<sum<<" ";
  }
  while(currentR <= R) {
   add(currentR);
   currentR++;
   //cout<<sum<<" ";
  }
  while(currentR > R+1) {
   remove(currentR-1);
   currentR--;
   //cout<<sum<<" ";
  }
  ans[q[i].i] = mymap[S];
  //cout<<endl;
 }

 for(int i=0; i<m; i++)
  printf("%d\n", ans[i]);
}

















Question 3: Link To Question (Similar to Mo) 



Each query consists of two integers  and .



For each query, you have to consider all the elements of array greater than or equal to , in original order of occurrence in array  and then find the  element from the selected elements. 



Solution: 




#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

struct node{
    int L,K,i;
}q[100005];

bool cmp(struct node a,struct node b){
    if(a.L != b.L)
            return a.L< b.L;
    return a.K<b.K;
}

int ans[100005];
int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,m;
    cin>>n>>m;
    int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<m;i++){
        cin>>q[i].L>>q[i].K;
        q[i].i=i;
    }
    sort(q,q+m,cmp);
    int lstL = -1,pos=0,lstK=0,kdiff;
    for(int i=0;i<m;i++){
        int L=q[i].L,K=q[i].K;
        //cout<<L<<" "<<K<<endl;
        if(L!=lstL){
            // pos=0;
            // while(pos<n && a[pos]!=L)
            //     pos++;
            lstL=L;
            lstK=0;
            pos=0;
        }
        //cout<<pos<<" "<<a[pos]<<endl;
        kdiff=K-lstK;
        //cout<<"kdiff "<<kdiff<<endl;
        while(kdiff>0){
            if(a[pos++]>=L){
                kdiff--;
            }
            //pos++;
        }
        //cout<<pos<<" "<<a[pos-1]<<endl;
        lstK=K;
        ans[q[i].i]=a[pos-1];
    }
    for(int i=0;i<m;i++){
        cout<<ans[i]<<endl;
    }
    return 0;
}












Practice Problems:









Comments

Post a Comment

Popular posts from this blog

Lazy Propagation - Too lazy to update all at a time

Image
Sometimes problems will ask you to update an interval from  l to r , instead of a single element. One solution is to update all the elements one by one. Complexity of this approach will be  O(N)  per operation since where are  N  elements in the array and updating a single element will take  O(logN)  time. To avoid multiple call to update function, we can modify the update function to work on an interval. For example consider the node with value 27 in above diagram, this node stores sum of values at indexes from 3 to 5. If our update query is for range 2 to 5, then we need to update this node and all descendants of this node. With Lazy propagation, we update only node with value 27 and postpone updates to its children by storing this update information in separate nodes called lazy nodes or values. We create an array lazy[] which represents lazy node. Size of lazy[] is same as array that represents segment tree, which is tree[] in below cod...
Read more

Combinatorial Game Theory

Image
Sometimes we find questions where two Players say A and B play a game optimally and we have to find out who ultimately is going to win the game provided there are some constraints. These questions are generally branched under the topic Combinatorial Game Theory. And the speciality about these is that the coding part is relatively very small and easy. The key to the Game Theory problems is the hidden observations which can be sometimes very hard to find. First, we will look at the basic division of positions to winning and losing . Question:  Two players are playing a game with n stones where player 1 always plays first. The two players move in alternating turns and play optimally. In a single move, a player can remove either 1, 3 or 4 stones from the pile of stones. If a player is unable to make a move then that player loses the game. Given the number of stones, find and print the name of the winner. Approach:  As we can see positions 1, 3 and 4 are winning positions ...
Read more

XOR Problems using Trie

Image
A Trie because of its re Trie Val property can be used to solve many problems that require to find the maximum XOR values or problems involving XOR. In this post, we will discuss similar problems where Trie can be used to solve them. Reference Links: Tutorials on Trie   Lets Jump to some questions  : Question  1:   MAX_XOR Given an array of integers , we have to find two elements whose XOR is maximum. Explanation: We First insert our numbers as bits in the Trie as we go. Now for finding the max XOR we start from the MSB and check along.  Let's say our number Y is b1,b2...bn, where b1,b2.. are binary bits. We start from b1. Now for the XOR to be maximum, we'll try to make most significant bit 1 after taking XOR. So, if b1 is 0, we'll need a 1 and vice versa. In the trie, we go to the required bit side. If favorable option is not there, we'll go other side. Doing this all over for i=1 to n, we'll get the maximum XOR possible. ...
Read more