【主席树】【区间不重复数个数】

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;

struct node {
	int ls, rs, sum;
} ns[MAXN * 20];

int ct;
int rt[MAXN * 20];

void cpy(int& now, int old) {
	now = ++ct;
	ns[now] = ns[old];
}

void pushUp(int now) {
	ns[now].sum = ns[ns[now].ls].sum + ns[ns[now].rs].sum;
}

void build(int& now, int l, int r) {
	now = ++ct;
	ns[now].sum = 0;
	if (l == r) return;
	int m = (l + r) >> 1;
	build(ns[now].ls, l, m);
	build(ns[now].rs, m + 1, r);
}

int update( int old, int l, int r, int pos,int val) {
	int now;
	cpy(now, old);
	if (l == r) {
		ns[now].sum+=val;
		return now;
	}
	int m = (l + r) >> 1;
	if (pos <= m)ns[now].ls = update(ns[old].ls, l, m, pos, val);
	else ns[now].rs = update(ns[old].rs, m + 1, r, pos, val);
	pushUp(now);
	return now;
}

int query(int l,int r,int now,int pos) {
	if (l == r) return ns[now].sum;
	int m = (l + r) >> 1;
	if (pos <= m) return ns[ns[now].rs].sum + query(l, m, ns[now].ls, pos);
	return query(m+1,r,ns[now].rs,pos);
}

void init(int n) {
	ct = 0;
	build(rt[0], 1, n);
}

int a[MAXN], b[MAXN];

int main() {
	int n, m;
	while (~scanf("%d",&n)) {
		for (int i = 1; i <= n; i++) {
			scanf("%d", &a[i]);
		}
		map<int, int>mp;
		init(n);
		for (int i = 1; i <= n; i++) {
	
			if (!mp[a[i]]) {
				rt[i] = update(rt[i - 1], 1, n, i, 1);
			}
			else {
				int tmp = update(rt[i - 1], 1, n, mp[a[i]], -1);
				rt[i] = update(tmp, 1, n, i, 1);
			}
			mp[a[i]] = i;
		}
		scanf("%d", &m);
		while (m--) {
			int s, t;
			scanf("%d%d", &s, &t);
			printf("%d\n", query(1, n, rt[t], s));
		}
	}
}