RT，这道题本来想卡掉莫队，结果把普通常数的主席树卡掉了，莫队还能 AC，甚至比我写的主席树还快（莫队 $5.59s$，主席树 $6.40s$）。

同时希望管理员能构造数据卡掉现有可 AC 块长（包括 $1.2 \times 10^3$、$1620$、$1725$、$2 \times 10^3$、$2025$ 等）。

代码：

#include <algorithm>
#include <cstdio>

using namespace std;

typedef unsigned int uint;

typedef struct {
	uint id;
	uint pos;
	uint l;
	uint r;
} Query;

const uint block = 1725;
uint a[1000007], cnt[1000007], ans[1000007];
Query query[1000007];

namespace Fread {
	const uint BUFFER_SIZE = 1 << 25;
	char buffer[BUFFER_SIZE + 7];
	char *pstart = buffer, *pend = buffer;

	#define _getchar() pstart < pend ? *pstart++ : ((pstart == (pend = (pstart = buffer) + fread(buffer, 1, BUFFER_SIZE, stdin))) ? EOF : *pstart++)

	inline uint read(){
		uint 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;
	}
}

bool operator <(const Query a, const Query b){
	return a.pos ^ b.pos ? a.pos < b.pos : a.pos & 1 ? a.r < b.r : a.r > b.r;
}

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

int main(){
	register uint n = Fread::read(), m, cur_ans = 0;
	for (register uint i = 1; i <= n; ++i){
		a[i] = Fread::read();
	}
	m = Fread::read();
	for (register uint i = 1; i <= m; ++i){
		query[i].l = Fread::read();
		query[i].r = Fread::read();
		query[i].id = i;
		query[i].pos = (query[i].l - 1) / block + 1;
	}
	sort(query + 1, query + m + 1);
	for (register uint i = 1, j = 1, k = 0; i <= m; ++i){
		while (j > query[i].l) cur_ans += !cnt[a[--j]]++;
		while (k < query[i].r) cur_ans += !cnt[a[++k]]++;
		while (j < query[i].l) cur_ans -= !--cnt[a[j++]];
		while (k > query[i].r) cur_ans -= !--cnt[a[k--]];
		ans[query[i].id] = cur_ans;
	}
	for (register uint i = 1; i <= m; ++i){
		write(ans[i]);
		putchar('\n');
	}
	return 0;
}