• Я хочу рассказать о очень тупой и бесполезной структуре данных — дерево отрезков на bitset.
• В чём смысл?-мы сможем решать количество уникальных чисел на отрезке за O(log n * x/logx)(на запрос ответа и изменения), где n-длина массива, а x-максимальное значение элемента массива.
• Если в массиве есть отрицательные числа — просто прибавьте ко всем числам abs(X), где X-минимальный элемент
• Вот код(если будут идеи оптимизации — пишите )

#include <bits/stdc++.h>
using namespace std;
vector<bitset<1000>> tree;
bitset<1000> getsum(int v, int Tl, int Tr, int l, int r){
	if(l>r)return 0;
	if(Tl==l&&Tr==r){
		return tree[v];
	}
	int Tm=(Tl+Tr)>>1;
	return getsum(v<<1,Tl,Tm,l,min(Tm,r))|getsum(v<<1|1,Tm+1,Tr,max(Tm+1,l),r);
}
int m=1, x;
void update(int v,int val){
	v+=m;
	tree[v]=0;
	tree[v][m]=1;
	v>>=1;
	while(v){
		tree[v]=tree[v<<1]|tree[v<<1|1];
		v>>=1;
	}
}
void solve(){
 	int n;
	cin>>n;
	while(m<n){
		m<<=1;
	}
	tree.resize(m<<1);
	for(int i=0;i<n;i++){
		x=(rand()%1000+1000)%1000;
		cout<<x<<' ';
		tree[i+m][x]=1;
	}
	for(int i=m-1;i>=1;i--){
		tree[i]=tree[i<<1]|tree[i<<1|1];
	}
	cout<<endl;
	int q, l, r;
	cin>>q;
	while(q--){
		cin>>l>>r;
		--l;--r;
		cout<<getsum(1,0,m-1,l,r).count()<<'\n';
	}
}                    
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);         	                  
	cout.tie(0);
	int t=1;
	//cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

На самом деле предела этой структуре данных нет. Можно реализовать K-я статистика на отрезке