how the function sort is working in the mo's algorithim in following code

general
,
1

#include
#include
#include
using namespace std;

#define N 311111
#define A 1111111
#define BLOCK 555 // ~sqrt(N)

int cnt[A], a[N], ans[N], answer = 0;

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]] == 1) {
		answer++;
	}
}

void remove(int position) {
	cnt[a[position]]--;
	if(cnt[a[position]] == 0) {
		answer--;
	}
}

int main() {
	int n;
	scanf("%d", &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;
		while(currentL < L) {
			remove(currentL);
			currentL++;
		}
		while(currentL > L) {
			add(currentL-1);
			currentL--;
		}
		while(currentR <= R) {
			add(currentR);
			currentR++;
		}
		while(currentR > R+1) {
			remove(currentR-1);
			currentR--;
		}
		ans[q[i].i] = answer;
	}

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

someone pls explain the working of sort in the mo’s algorithm @vijju123

3

question of spoj //www.spoj.com/problems/DQUERY/

4

finally got understood it is sorting structure with respect to value of L and if value of L is same then we sort with less value of R

5

There is a even better optimization to this standard algo, which @meooow discussed in some deep and dark depths of this forum. Feeling up for a hunt? :stuck_out_tongue:

2 Likes
6


I call it @meooow’s Algorithm :stuck_out_tongue:

1 Like
7

thank u so much

8

i would be glad if u let me k ow what is difference bw mo’s algo and sqareroot decomposition @vijju123 @dishant_18

9

Mo’s decomposition is a specialized type of square decomposition to use when all queries are available before hand, and when the question satisfies Mo’s conditions.

1 Like
10

In addition to what @vijju123 said, Mo’s algorithm can only be used when there are no updates involved. Also, Mo’s algorithm is an offline algorithm whereas squareroot decomposition is an online algorithm!