莫队模板

显然，下面的代码是求 ([l..r]) 中不同颜色的种数
其中 (block = frac{n}{sqrt{frac 2 3 m}})
且奇数块中按 (a.r > b.r) 排（首块为偶数块）
依然显然，它过不了 ([SDOI2009]HH) 的项链 这一题

(Code)

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;

const int N = 1e6 + 5;
int n , m , a[N] , bl , ans , Ans[N] , cnt[N];
struct ask{
	int l , r , id;
}q[N];

inline int read()
{
	char ch = getchar(); int res = 0;
	while (ch < '0' || ch > '9') ch = getchar();
	while (ch >= '0' && ch <= '9') 
		res = (res << 3) + (res << 1) + ch - '0' , ch = getchar();
	return res;
}
inline bool cmp(ask a , ask b){
	return (a.l / bl) ^ (b.l / bl) ? (a.l < b.l) : (((a.l / bl) & 1) ? a.r < b.r : a.r > b.r);
}
inline void add(int x)
{
	if (cnt[a[x]] == 0) ++ans;
	++cnt[a[x]];
}
inline void del(int x)
{
	--cnt[a[x]];
	if (cnt[a[x]] == 0) --ans;
}

int main()
{
	n = read();
	for(register int i = 1; i <= n; i++) a[i] = read();
	m = read();
	for(register int i = 1; i <= m; i++) 
		q[i].l = read() , q[i].r = read() , q[i].id = i;
	bl = n / sqrt(m * 2 / 3);
	sort(q + 1 , q + m + 1 , cmp);
	int l = 0 , r = 0 , ql , qr;
	for(register int i = 1; i <= m; i++)
	{
		ql = q[i].l , qr = q[i].r;
		while (l > ql) add(--l);
		while (l < ql) del(l++);
		while (r > qr) del(r--);
		while (r < qr) add(++r);
		Ans[q[i].id] = ans;
	}
	for(register int i = 1; i <= m; i++) printf("%d
" , Ans[i]);
}