跟题解中维护的都不一样 我维护的是 这个值出现的次数 在查询时查到叶子节点，做查分求解

#include<bits/stdc++.h>
using namespace std;

const int N=1e6+10;

int n,cnt;
int a[N],tr[N];
struct T{
	int l,r;
	int sum;
}t[N*100];

int build(int l,int r)
{
	int p=++cnt;
	if(l==r)
		return p;
	int mid=l+r>>1;
	t[p].l=build(l,mid);
	t[p].r=build(mid+1,r);
}
int update(int p,int l,int r,int x)
{
	int u=++cnt;
	t[u].l=t[p].l,t[u].r=t[p].r;t[u].sum=t[p].sum;
	if(l==r)
	{
		t[u].sum++;
		return u;
	}
	int mid=l+r>>1;
	if(x<=mid)	t[u].l=update(t[p].l,l,mid,x);
	else t[u].r=update(t[p].r,mid+1,r,x);
	return u;
}
int query(int u1,int u2,int L,int R)
{
	if(L==R)
	{
	//	cout<<"   "<<L<<" "<<t[u1].sum<<" "<<t[u2].sum<<endl;
		if(t[u2].sum-t[u1].sum)
			return 1;
		else return 0;
	}
	int mid=L+R>>1,res=0;
	res+=query(t[u1].l,t[u2].l,L,mid);
	res+=query(t[u1].r,t[u2].r,mid+1,R);
	return res;
}

int main()
{
	scanf("%d",&n);
	int mx=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		mx=max(mx,a[i]);
	}
	tr[0]=build(1,mx);
	for(int i=1;i<=n;i++)
		tr[i]=update(tr[i-1],1,mx,a[i]);
	int m;
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		printf("%d\n",query(tr[l-1],tr[r],1,mx));
	}
	return 0;
}