Mo's Algorithm

mo.cpp

// http://codeforces.com/group/kZPk3ZTzR5/contest/101041/problem/D
// Nome do problema: Investigating the cartel
// Descrição: Quantos elementos com frequência maior que 1 no intervalo

// https://www.codepit.io/#/problems/5369c356f6fa9de49e5c7fa3/view
// Nome do problema: D-query
// Descrição: Quantos elementos diferentes no intervalo

// Resolve consultas em O((N+Q)*sqrt(N)+Q*log(Q))
#include <bits/stdc++.h>
using namespace std;

int n, q, block, tot;
int freq[1000006], a[30004];

struct Query {
	int l, r, idx, bl, ans;
};
Query queries[200005];

inline void sub(int i) {
	tot -= (--freq[a[i]] == 0);
}

inline void add(int i) {
	tot += (++freq[a[i]] == 1);
}

inline void mo() {
	sort(queries+1, queries+1+q, [](Query a, Query b)->bool {
		if (a.bl != b.bl) return a.bl < b.bl;
		return a.r < b.r;
	});
	
	int l, r, cur_l = 0, cur_r = 0;
	for (int i = 1; i <= q; i++) {
		l = queries[i].l;
		r = queries[i].r;
		while (cur_l < l) sub(cur_l++);
		while (cur_l > l) add(--cur_l);
		while (cur_r < r) add(++cur_r);
		while (cur_r > r) sub(cur_r--);
		queries[i].ans = tot;
	}
	
	sort(queries+1, queries+1+q, [](Query a, Query b)->bool {
		return a.idx < b.idx;
	});
}

int main() {
	cin >> n;
	block = sqrt(n);
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	
	cin >> q;
	for (int i = 1; i <= q; i++) {
		cin >> queries[i].l >> queries[i].r;
		queries[i].bl = queries[i].l/block;
		queries[i].idx = i;
	}
	
	mo();
	
	for (int i = 1; i <= q; i++) {
		cout << queries[i].ans << '\n';
	}

	return 0;
}