RT，蒟蒻初学主席树，被卡常了 /kk

代码：

#include <stdio.h>

typedef struct {
	int l;
	int r;
	int cnt;
} Node;

int id = 0;
int a[1000007], root[1000007], pre[1000007];
Node tree[44000007];

namespace Fread {
	const int BUFFER_SIZE = 1 << 24;
	char buffer[BUFFER_SIZE + 7];
	char *pstart = buffer, *pend = buffer;
	
	#define _getchar() pstart == pend ? ((pstart == (pend = (pstart = buffer) + fread(buffer, 1, BUFFER_SIZE, stdin))) ? EOF : *pstart++) : *pstart++
	
	inline int read(){
		int ans = 0;
		char ch = _getchar();
		while (ch < '0' || ch > '9'){
			ch = _getchar();
		}
		while (ch >= '0' && ch <= '9'){
			ans = (ans << 3) + (ans << 1) + (ch ^ 48);
			ch = _getchar();
		}
		return ans;
	}
}

int build(int l, int r){
	int x = ++id;
	if (l != r) tree[x].l = build(l, (l + r) >> 1), tree[x].r = build(((l + r) >> 1) + 1, r);
	return x;
}

int insert(int x, int l, int r, int k, int val){
	int y = ++id;
	tree[y] = tree[x];
	tree[y].cnt += val;
	if (l != r) k <= (l + r) >> 1 ? tree[y].l = insert(tree[x].l, l, (l + r) >> 1, k, val) : tree[y].r = insert(tree[x].r, ((l + r) >> 1) + 1, r, k, val);
	return y;
}

int query(int x, int l, int L, int R){
	return L == R ? tree[x].cnt : (l <= (L + R) >> 1 ? query(tree[x].l, l, L, (L + R) >> 1) + tree[tree[x].r].cnt : query(tree[x].r, l, ((L + R) >> 1) + 1, R));
}

void write(int n){
	if (n >= 10) write(n / 10);
	putchar(n % 10 + '0');
}

int main(){
	int n = Fread::read(), m;
	for (register int i = 1; i <= n; i++){
		a[i] = Fread::read();
	}
	root[0] = build(1, n);
	for (register int i = 1; i <= n; i++){
		if (pre[a[i]] == 0){
			root[i] = insert(root[i - 1], 1, n, i, 1);
		} else {
			root[i] = insert(insert(root[i - 1], 1, n, pre[a[i]], -1), 1, n, i, 1);
		}
		pre[a[i]] = i;
	}
	m = Fread::read();
	for (register int i = 1; i <= m; i++){
		int l = Fread::read(), r = Fread::read();
		write(query(root[r], l, 1, n));
		putchar('\n');
	}
	return 0;
}