Shared code

#pragma optimize(3)
#include <bits/stdc++.h>
 
//#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
using namespace std;
 
const int N = 2e5+5;
int k;

int cnt[N];
int a[N], bid[N], l = 1, r = 0, tmp= 0;
	
struct query{
	int l,r, id;
	bool operator < (const query b){
		return (l/k == b.l/k ? r < b.r : l/k < b.l/k);
	}
};
 
void add(int pos){
	if(!cnt[a[pos]]) tmp++;
	cnt[a[pos]]++;
}
 
void sub(int pos){
	--cnt[a[pos]];
	if(!cnt[a[pos]]) tmp--;
}
 
signed main(){
	fastio
	int n,mm;
	cin >> n >> mm;
	k = sqrt(n)+1;
	for(int i = 1;i <= n;i++) cin >> a[i];
	vector<int> v(a+1,a+n+1);
	sort(v.begin(),v.end());
	v.resize(unique(v.begin(),v.end())-v.begin());
	for(int i = 1;i <= n;i++){
		a[i] = lower_bound(v.begin(),v.end(),a[i])-v.begin();
	}
	vector<query> Q;
	int ans[mm];
	for(int i = 0;i < mm;i++){
		int ql, qr;
		cin >> ql >> qr;
		Q.push_back({ql,qr,i});
	}
	sort(Q.begin(),Q.end());
	for(auto q : Q){
		while(l < q.l) sub(l++);
		while(l > q.l) add(--l);
		while(r < q.r) add(++r);
		while(r > q.r) sub(r--);
		ans[q.id] = tmp;
	}
	for(auto x : ans) cout << x << "\n";
}