如果我们要由 f_{i,i} 求出 f_{i,j}，那么我们还需要一些量：我们要知道第 i 个数左边第一个和它相同的数的位置 l_i 以及右边的第一个 r_i。那么我们就可以求出 f 数组。
预处理完毕后就可以读入询问了，对于一个询问 [a,b]，我们先求出 [a,b] 所在的块 fa,fb，连续的整块 fa+1，到 fb-1 可以 O(1) 得到就是 f_{fa+1,fb-1}，之后暴力求出 a 所在块以及 b 所在块内出现的加到 res 中即可，需要用到之前求出的 l 以及 r 数组。
实现
对于 f 数组我们可以这么求：
## 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
inline void write(int x){
if(x==0){putchar('0');return;}
int len=0,k1=x,c[10005];
if(k1<0)k1=-k1,putchar('-');
while(k1)c[len++]=k1%10+'0',k1/=10;
while(len--)putchar(c[len]);
}
const int N=1e6+5,M=1e3+5;
int w[N],f[M][M],l[N],r[N],last[N];
bitset<N>vis;
int main(){
int n=read(),num=ceil(sqrt(n)),siz=floor(sqrt(n));
memset(r,0x3f,sizeof r);
for(int i=1;i<=n;i++){
w[i]=read();
l[i]=last[w[i]];
last[w[i]]=i;
r[l[i]]=i;
}
for(int i=1;i<=num;i++){
vis.reset();
int beg=(i-1)*siz+1,end=min(i*siz,n);
for(int j=beg;j<=end;j++){
f[i][i]+=!vis[w[j]];
vis[w[j]]=1;
}
}
for(int i=1;i<num;i++){
for(int j=1;i+j<=num;j++){
f[j][i+j]=f[j+1][i+j];
int beg=(j-1)*siz+1,end=j*siz;
int border=(i+j)*siz;
for(int k=beg;k<=end;k++){
f[j][i+j]+=(r[k]>border);
}
}
}
int m=read();
while(m--){
int a=read(),b=read();
int fa=a/siz+1,fb=b/siz+1;
int res=f[fa+1][fb-1];
if(fb-fa<=1){
vis.reset();
for(int i=a;i<=b;i++){
res+=!vis[w[i]];
vis[w[i]]=1;
}
write(res),puts("");
continue;
}
int rb=(fb-1)*siz;
int enda=fa*siz,begb=(fb-1)*siz+1;
for(int i=a;i<=enda;i++)res+=(r[i]>rb);
for(int i=begb;i<=b;i++)res+=(l[i]<a);
write(res),puts("");
}
return 0;
}
```