参考了第三篇题解

#include<bits/stdc++.h>
#define lchild (root << 1)
#define rchild ((root << 1) + 1)
using namespace std;
const int N = 1e6 + 9,M = 1e6 + 9;
int n,m;
int a[N],last[N];
int tree[N],ans[N];
vector<int> vis[N];
struct queries{
	int l,r,id;
}q[M];
bool cmp(queries a,queries b){
	return a.r < b.r;
}
void push_up(int root){
	tree[root] = tree[lchild] + tree[rchild];
}
void update(int root,int l,int r,int k,int v){
	if(l == r){
		tree[root] = v;
		return;
	}
	int mid = (l + r) >> 1;
	if(k <= mid)
		update(lchild,l,mid,k,v);
	else
		update(rchild,mid + 1,r,k,v);
	push_up(root);
}
bool in_range(int l,int r,int now_l,int now_r){
    return l <= now_l && now_r <= r;
}
bool out_range(int l,int r,int now_l,int now_r){
    return now_r < l || now_l > r;
}
int query(int root,int l,int r,int now_l,int now_r){
	if(l == now_l && r == now_r)
		return tree[root];
	int mid = (l + r) >> 1;
	if(now_r <= mid)
		return query(lchild,l,mid,now_l,now_r);
	else if(mid < now_l)
		return query(rchild,mid + 1,r,now_l,now_r);
	else
		return query(lchild,l,mid,now_l,mid) + query(rchild,mid + 1,r,mid + 1,now_r);
	return 0;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n;
	for(int i = 1;i <= n;i++)
		cin >> a[i];
	cin >> m;
	for(int i = 1;i <= m;i++){
		cin >> q[i].l >> q[i].r;
		q[i].id = i;
	}
	sort(q + 1,q + m + 1,cmp);
	for(int i = 1;i <= m;i++)
		vis[q[i].r].push_back(i);
	for(int i = 1;i <= n;i++){
		if(!last[a[i]]){
			last[a[i]] = i;
			update(1,1,n,i,1);
		}
		else{
			update(1,1,n,last[a[i]],0);
			last[a[i]] = i;
			update(1,1,n,i,1);
		}
		for(int j = 0;j < (int)vis[i].size();j++){
			int tmp = vis[i][j];
			ans[q[tmp].id] = query(1,1,n,q[tmp].l,q[tmp].r);
		}
	}
	for(int i = 1;i <= m;i++)
		cout << ans[i] << '\n';
	return 0;
}