rt，TLE #8 #9 #10

不知道是不是解法问题

#include<bits/stdc++.h>
using namespace std;
struct node
{
	int sum,ls,rs;
}tr[25*1000005];
int tot,n,m,rt[1000005];
struct bk
{
	int col,id,ne;
}a[1000005];
bool cmp1(bk a1,bk a2)
{
	if(a1.col==a2.col) return a1.id<a2.id;
	else return a1.col<a2.col;
}
bool cmp2(bk a1,bk a2)
{
	return a1.id<a2.id;
}
int build(int l,int r)
{
	int p=++tot;
	if(l==r) return p;
	int mid=(l+r)/2;
	tr[p].ls=build(l,mid);
	tr[p].rs=build(mid+1,r);
	return p;
}
int update(int k,int l,int r,int pos,int v)
{
	int p=++tot;
	tr[p]=tr[k];
	if(l==r)
	{
		tr[p].sum+=v;
		return p;
	}
	int mid=(l+r)/2;
	if(pos<=mid) tr[p].ls=update(tr[p].ls,l,mid,pos,v);
	else tr[p].rs=update(tr[p].rs,mid+1,r,pos,v);
	tr[p].sum=tr[tr[p].ls].sum+tr[tr[p].rs].sum;
	return p;
}
int query(int k,int l,int r,int L,int R)
{
	if(L<=l&&r<=R) return tr[k].sum;
	int mid=(l+r)/2,res=0;
	if(L<=mid) res+=query(tr[k].ls,l,mid,L,R);
	if(mid+1<=R) res+=query(tr[k].rs,mid+1,r,L,R);
	return res;
}
int main()
{
	scanf("%d",&n),rt[0]=build(1,1e6+1);
	for(int i=1;i<=n;i++) 
		scanf("%d",&a[i].col),a[i].id=i;
	sort(a+1,a+n+1,cmp1);
	for(int i=1;i<=n;i++)
	{
		if(a[i].col==a[i+1].col) a[i].ne=a[i+1].id;
		else a[i].ne=n+1;
	}
	sort(a+1,a+n+1,cmp2);
	for(int i=1;i<=n;i++) rt[i]=update(rt[i-1],1,1e6+1,a[i].ne,1);
	scanf("%d",&m);
	for(int i=1,l,r;i<=m;i++)
	{
		scanf("%d%d",&l,&r);
		printf("%d\n",query(rt[r],1,1e6+1,r+1,n+1)-query(rt[l-1],1,1e6+1,r+1,n+1));
	}
	return 0;
}