来一个乱搞题解:

先分块，然后散块暴力查，整块开 ST 表合并 bitset， 复杂度 $O(n \sqrt n \times \frac{\log n}{w} + \frac{n \times q}{w})$

然后就过了

#include<bits/stdc++.h>
using namespace std;
namespace IO{
	const int SIZE=1<<21;
	static char ibuf[SIZE],obuf[SIZE],*iS,*iT,*oS=obuf,*oT=oS+SIZE-1;
    int qr;
    char qu[55],c;
    bool f;
	#define getchar() (IO::iS==IO::iT?(IO::iT=(IO::iS=IO::ibuf)+fread(IO::ibuf,1,IO::SIZE,stdin),(IO::iS==IO::iT?EOF:*IO::iS++)):*IO::iS++)
	#define putchar(x) *IO::oS++=x,IO::oS==IO::oT?flush():0
	#define flush() fwrite(IO::obuf,1,IO::oS-IO::obuf,stdout),IO::oS=IO::obuf
	#define puts(x) IO::Puts(x)
	template<typename T>
    inline void read(T&x){
    	for(f=1,c=getchar();c<48||c>57;c=getchar())f^=c=='-';
    	for(x=0;c<=57&&c>=48;c=getchar()) x=(x<<1)+(x<<3)+(c&15); 
    	x=f?x:-x;
    }
    template<typename T>
    inline void write(T x){
        if(!x) putchar(48); if(x<0) putchar('-'),x=-x;
        while(x) qu[++qr]=x%10^48,x/=10;
        while(qr) putchar(qu[qr--]);
    }
    inline void Puts(const char*s){
    	for(int i=0;s[i];i++)
			putchar(s[i]);
		putchar('\n');
	}
	struct Flusher_{~Flusher_(){flush();}}io_flusher_;
}
using IO::read;
using IO::write;
const int warma = 200;
const int maxn = 3e4+13;
bitset<maxn> st[220][10];
int a[maxn],n,q;
inline void init(){
    for(int i=1;i<=n;i=-~i){
        st[(i-1)/warma+1][0][a[i]]=1;
    }
    for(int j=1;j<=8;j=-~j)
        for(int i=1;i+(1<<j)-1<=210;i=-~i)
            st[i][j]=st[i][j-1]|st[i+(1<<(j-1))][j-1];
}
bitset<maxn> ans;
inline void query(int l,int r){
    int bl=(l-1)/warma+1;
    int br=(r-1)/warma+1;
    if(bl==br){
        for(int i=l;i<=r;i=-~i){
            ans[a[i]]=1;
        }
        return ;
    }
    if(br!=bl+1){
        int k=log2((br-1)-(bl+1)+1);
        ans|=(st[bl+1][k]|st[(br-1)-(1<<k)+1][k]);
    }
    for(int i=l;i<=bl*warma;i=-~i){
        ans[a[i]]=1;
    }
    for(int i=r;i>=(br-1)*warma+1;--i){
        ans[a[i]]=1;
    }
}
int tot;
map<int,int> lsh;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    read(n);
    for(int i=1;i<=n;i++){
        read(a[i]);
        if(lsh[a[i]]==0) lsh[a[i]]=++tot;
        a[i]=lsh[a[i]];
    }
    read(q);
    init();
    for(int i=1;i<=q;i++){
        int l,r;
        read(l);
        read(r);
        ans.reset();
        query(l,r);
        write(ans.count());
        putchar('\n');
    }
}