12Pts 离线+线段树

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 5;
int a[N];
struct A{
	int l,r;
	int id;
	int v;
}p[N];
int t[N<<2];
int lazy[N<<2];
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
void pushup(int k){
	t[k]=t[k<<1]+t[k<<1|1];
}
void pushdown(int k,int num){
	if(lazy[k]){
		t[k<<1]+=lazy[k]*(num-(num>>1));
		t[k<<1|1]+=lazy[k]*(num>>1);//！！！！！！
		lazy[k<<1]+=lazy[k];
		lazy[k<<1|1]+=lazy[k];
		lazy[k]=0;
	}
	return ;
}
void updata(int L,int R,int l,int r,int k,int v){
	if(L<=l&&r<=R){
		lazy[k]+=k,t[k]+=v*(r-l+1);
		return ;
	}
	int num=r-l+1;
	pushdown(k,num);
	int m=l+((r-l)>>1);
	if(L<=m)updata(L,R,l,m,k<<1,v);
	if(m<R)updata(L,R,m+1,r,k<<1|1,v);
	pushup(k);
	return ;
}
long long query(int L,int R,int l,int r,int k){
	if(L<=l&&r<=R){
		return t[k];
	}
	int num=r-l+1;
	pushdown(k,num);
	int res=0;
	int m=l+((r-l)>>1);
	if(L<=m)res+=query(L,R,l,m,k<<1);
	if(m<R)res+=query(L,R,m+1,r,k<<1|1);
	return res;
}
bool cmp(A a,A b){
	if(a.r!=b.r)return a.r<b.r;
	return a.l<b.l;
}
bool ccmp(A a,A b){return a.id<b.id;}
map<int,int>la;
main(){
	int n=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
	}
	int m=read();
	
	for(int i=1;i<=m;i++){
		p[i].l=read(),p[i].r=read();
		p[i].id=i;
	}
	sort(p+1,p+1+m,cmp);
	for(int i=1;i<=m;i++){
		int nw=1;
		while(nw<=p[i].r){
			if(la[a[nw]]){
				updata(la[a[nw]],la[a[nw]],1,n,1,-1);
			}
			la[a[nw]]=nw;
			updata(la[a[nw]],la[a[nw]],1,n,1,1);
			nw++;
		}
		p[i].v=query(p[i].l,p[i].r,1,n,1);
	}
	sort(p+1,p+1+m,ccmp);
	for(int i=1;i<=m;i++)printf("%lld\n",p[i].v);
	return 0;
}