复杂度是没问题的，只不过毒瘤数据加上线段树常数有点大，好心人帮孩子卡一下常吧
题目:HH的项链
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+3;
int cnt,vcnt;
int n,m,a[N],b[N],root[N];
map<int,int> mp;
inline int read(){
int f=1,x=0;char s=getchar();
while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();};
while(s<='9'&&s>='0'){x=x*10+(s-'0');s=getchar();}
return x*f;
}
inline void write(int x)
{
if(x<0)
putchar('-'),x=-x;
if(x>9)
write(x/10);
putchar(x%10+'0');
putchar('\n');
return;
}
struct tree{
int l,r,val;
}pst[N<<5];
int update(int pre,int pl,int pr,int x,int val){
int rt=++cnt;
pst[rt].l=pst[pre].l;
pst[rt].r=pst[pre].r;
pst[rt].val=pst[pre].val+val;
//cout<<"pst:"<<pst[rt].val<<endl;
int mid=(pl+pr)>>1;
if(pl<pr){
if(x<=mid) pst[rt].l=update(pst[pre].l,pl,mid,x,val);
else pst[rt].r=update(pst[pre].r,mid+1,pr,x,val);
}
return rt;
}
int query(int node,int pl,int pr,int l,int r){
if(l<=pl&&pr<=r) return pst[node].val;
int res=0,mid=(pl+pr)>>1;
if(l<=mid) res+=query(pst[node].l,pl,mid,l,r);
if(mid+1<=r) res+=query(pst[node].r,mid+1,pr,l,r);
return res;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) {a[i]=read();}
for(int i=n;i>=1;i--){
if(mp[a[i]]){
//cout<<"i:"<<i<<endl;
//cout<<mp[a[i]]<<endl;
root[i]=update(root[i+1],1,n,mp[a[i]],-1);//值改为0
root[i]=update(root[i],1,n,i,1);
}
else{
root[i]=update(root[i+1],1,n,i,1);
}
mp[a[i]]=i;
}
cin>>m;
while(m--){
int l,r;
l=read();r=read();
write(query(root[l],1,n,1,r));
}
return 0;
}
