@[zhouxi2022HZO](/user/876268) 如果不出意外的话，我记得这题似乎是卡莫队的。不过您也可以试一试再卡卡常
by blue_wine @ 2024-03-25 21:17:23
用线段树吧（蒟蒻不会莫队）
```
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define maxn (int)1e6
#define maxm (int)1e6
int n,m;
struct NODE
{
int l,r;
long long sum;
}t[4*maxn+100];
int a[maxn+100],cnt[maxn+100],lst[maxn+100],ans[maxn+100];
struct Qst{int id,l,r;}q[maxm+100];
vector<int>vis[maxn+100];
void build(int p,int l,int r)
{
t[p].l=l;
t[p].r=r;
if(l==r)return;
int mid=(l+r)/2;
build(2*p,l,mid);
build(2*p+1,mid+1,r);
return;
}
void change(int p,int x,long long v)
{
if(t[p].l==t[p].r)
{
t[p].sum=v;
return;
}
int mid=(t[p].l+t[p].r)/2;
if(x<=mid)change(2*p,x,v);
else change(2*p+1,x,v);
t[p].sum=t[2*p].sum+t[2*p+1].sum;
return;
}
long long get(int p,int l,int r)
{
if(l<=t[p].l&&t[p].r<=r)return t[p].sum;
int mid=(t[p].l+t[p].r)/2;
long long sum=0;
if(l<=mid)sum+=get(2*p,l,r);
if(r>=mid+1)sum+=get(2*p+1,l,r);
return sum;
}
bool cmp(Qst a,Qst b){return a.r<b.r;}
int main()
{
cin>>n;
build(1,1,n);
for(int i=1;i<=n;i++)cin>>a[i];
cin>>m;
for(int i=0;i<m;i++)
{
cin>>q[i].l>>q[i].r;
q[i].id=i;
}
sort(q,q+m,cmp);
for(int i=0;i<m;i++)vis[q[i].r].push_back(i);
for(int i=1;i<=n;i++)
{
if(lst[a[i]])change(1,lst[a[i]],0);
lst[a[i]]=i;
change(1,i,1);
for(int j=0;j<vis[i].size();j++)
{
int tmp=vis[i][j];
ans[q[tmp].id]=get(1,q[tmp].l,q[tmp].r);
}
}
for(int i=0;i<m;i++)cout<<ans[i]<<"\n";
return 0;
}
```
by Lawrence001 @ 2024-03-25 21:25:50
> 本题可能需要较快的读入方式，最大数据点读入数据约 20MB
cin关了同步还是比scanf慢
by ybc2027zhanglingrui @ 2024-04-08 22:15:40
@[ybc2027zhanglingrui](/user/1238483) 好吧用快读快写
by ybc2027zhanglingrui @ 2024-04-08 23:06:44
没写过，但莫队不是 $O(n \sqrt n)$ 嘛，好像题目底下 $40\%$ 数据的 $10^5$ 就是留给莫队的吧。
by Nighramet @ 2024-04-12 19:18:41
坏了我成小丑了，才发现楼主已经 $AC$ 了……而且还没看到时限有 $2s$。刚刚试了一下，不会卡常的我加个快读就有 [$60pts$](https://www.luogu.com.cn/record/155513457) ，好像还真可以……
by Nighramet @ 2024-04-12 20:42:16