TLE on #10

话说主席树的复杂度是对的吧，为啥也要卡

#include <cstdio>

#define maxn 1000005

inline char nc () {  
    static char buf[1 << 21], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread (buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
}

#define nc getchar

inline int read () {
    register int x(0), f(1); char ch = nc ();
    while (ch < '0' || ch > '9') {if (ch == '-') f = ~f +1; ch = nc ();}
    while (ch >= '0' && ch <= '9') {x = (x<<3) + (x<<1) + (ch^48); ch = nc ();}
    return x * f;
}

inline void write(int X)
{
	if(X<0) {X=~(X-1); putchar('-');}
	if(X>9) write(X/10);
	putchar(X%10+'0');
}

struct tree{
	int l, r, val;
}hjt[maxn * 22];

int top, n, m, a[maxn], root[maxn], next[maxn], head[maxn];

inline void change(int l, int r, int last, int &now, int k){
	hjt[now = ++top] = hjt[last];
	hjt[now].val++;
	if(l == r) return;
	register int mid = l + r >> 1;
	if(k <= mid) change(l, mid, hjt[last].l, hjt[now].l, k);
	else change(mid + 1, r, hjt[last].r, hjt[now].r, k); 
}

inline int ask(int l, int r, int L, int R, int k){
	if(l == r) return hjt[R].val - hjt[L].val;
	register int mid = l + r >> 1;
	if(k <= mid) return ask(l, mid, hjt[L].l, hjt[R].l, k) + hjt[hjt[R].r].val - hjt[hjt[L].r].val;
	else return ask(mid + 1, r, hjt[L].r, hjt[R].r, k);
}

int main(){
	scanf("%d",&n);
	for(register int i = 1; i <= n; i++){
		a[i] = read();
		if(head[a[i]]) next[head[a[i]]] = i;
		head[a[i]] = i;
	}
	for(register int i = 1; i <= n; i++){
		if(!next[i]) next[i] = n + 1;
		change(1, n + 1, root[i-1], root[i], next[i]);
    }
	scanf("%d",&m);
	for(register int i = 1, start, end; i <= m; i++){
		start = read(), end = read();
		write(ask(1, n + 1, root[start-1], root[end], end + 1));
		puts("");
	}
	return 0;
}