所以到底能不能用主席树做

#include <bits/stdc++.h>
#define mid ((l+r)>>1)
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch&15);ch=getchar();}
	return x*f;
}
const int N=5e6+7,M=5e7+7;
int n,m,arr[N],last[N],Root[N];
int cnt;
struct TREE{int ls,rs,sum;}tree[M];
void update(int &NEW,int OLD,int l,int r,int val){//主席树维护last位置上数的数量，所以LR范围取0-n即可
	NEW=++cnt;tree[NEW]=tree[OLD];tree[NEW].sum++;
	if(l==r) return;
	if(val<=mid) update(tree[NEW].ls,tree[OLD].ls,l,mid,val);
	if(val>=mid+1) update(tree[NEW].rs,tree[OLD].rs,mid+1,r,val);
}
int query(int x,int y,int l,int r,int idx){
//拿维护每个last值数量的主席树，前缀和出区间权值线段树后，计算区间内有多少last<idx
//我只要减出来的树中维护的值域<idx的部分
	if(l>=idx) return 0;
	if(r<idx) return tree[y].sum-tree[x].sum;
	return query(tree[x].ls,tree[y].ls,l,mid,idx)+query(tree[x].rs,tree[y].rs,mid+1,r,idx);
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++) arr[i]=read(),update(Root[i],Root[i-1],0,n,last[arr[i]]),last[arr[i]]=i;
	m=read();
	int x,y;
	for(int i=1;i<=m;i++){
		x=read(),y=read();
		printf("%d\n",query(Root[x-1],Root[y],0,n,x));
	}
	return 0;
}