刚学OI 114ms

求助有没有优化的方法可以用莫队过这题，看到好像很多块数都是可以过的。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;

#define endl '\n'

#define gc() (st==ed&&(ed=(st=buf)+fread(buf,1,100000,stdin),st==ed)?EOF:*st++)
char buf[100001],*st=buf,*ed=buf;
void read(int &a){
    a=0;char c=gc();
    while(c>'9'||c<'0')c=gc();
    while(c>='0'&&c<='9')a=a*10+c-48,c=gc();
}

const int N=1e6+5;
struct query{
	int id, l, r, k;
}q[N];

int w[N];
int n;
int len;
int cnt[N], ans[N];

bool cmp(const query& x, const query& y){
	return x.k!=y.k? x.k<y.k : x.r<y.r;
}

inline void add(int v, int& res){
	res+=++cnt[v]==1;
}

inline void del(int v, int& res){
	res-=--cnt[v]==0;
}

int main(){
	read(n);
	for(register int i=1; i<=n; i++) read(w[i]);
	
	int m; read(m);
	len=sqrt(double(n)*n/m);
	
	for(register int i=1; i<=m; i++){
		int l, r; read(l), read(r);
		q[i]={i, l, r, l/len};
	}
	
	sort(q+1, q+1+m, cmp);
	
	for(register int i=0, j=1, k=1, res=0; k<=m; k++){
		int id=q[k].id, l=q[k].l, r=q[k].r;
		while(i<r) add(w[++i], res);
		while(i>r) del(w[i--], res);
		while(j<l) del(w[j++], res);
		while(j>l) add(w[--j], res);
		ans[id]=res;
	}
	
	for(register int i=1; i<=m; i++) printf("%d\n", ans[i]);
	
    return 0;
}