上面这份代码是过不了的，而下面那份代码是过了的。

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define add(x) ans+=(!(cnt[x]++))
#define del(x) ans-=(!(--cnt[x]))
const int MAXN=1e6+10;
int n,Q;
int a[MAXN];
int cnt[MAXN];
int ans=0;
int len;
char *p1,*p2,buf[MAXN];
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++)
int iidx=0,iiidx[MAXN];
inline void read(int &x){
	char c;
	c=gc();
	while(c<'0'||c>'9'){
		c=gc();
	}
	while(c>='0'&&c<='9'){
		x=(x<<3)+(x<<1)+(c&15);
		c=gc();
	}
}
struct QUERY{
	int id,l,r;
}q[MAXN];
int answ[MAXN];
inline void write(int x){
	if(x<10){
		putchar(x|'0');
		return;
	}
	write(x/10);
	putchar(x%10|'0');
}
inline bool cmp(QUERY &H,QUERY &G){
	if(H.l/len!=G.l/len){
		return H.l/len<G.l/len;
	}
	if((H.l/len)&1){
		return H.r<G.r;
	}
	return H.r>G.r;
}
int main(){
	freopen("ring.in","r",stdin);
	freopen("ring.out","w",stdout);
	read(n);
	for(int i=1;i<=n;++i){
		read(a[i]);
//		if(!iiidx[a[i]]){
//			iiidx[a[i]]=++iidx;
//		}
//		a[i]=iiidx[a[i]];
	}
	read(Q);
	len=max(1,(int)(sqrt((double)(n)*n/(double)(Q))));
	for(int i=1;i<=Q;++i){
		read(q[i].l);read(q[i].r);
		q[i].id=i;
	}
	sort(q+1,q+Q+1,cmp);
	for(int k=1,i=0,j=1;k<=Q;++k){
		while(i<q[k].r){
			add(a[++i]);
		}
		while(i>q[k].r){
			del(a[i]),--i;
		}
		while(j<q[k].l){
			del(a[j]),++j;
		}
		while(j>q[k].l){
			add(a[--j]);
		}
		answ[q[k].id]=ans;
	}
	for(int k=1;k<=Q;++k){
		write(answ[k]);
		putchar('\n');
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}

这个代码会跑 $\text{TLE}$。而下面这份代码：

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define add(x) ans+=(!(cnt[x]++))
#define del(x) ans-=(!(--cnt[x]))
const int MAXN=1e6+10;
int n,Q;
int a[MAXN];
int cnt[MAXN];
int ans=0;
int len;
char *p1,*p2,buf[MAXN];
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++)
int iidx=0,iiidx[MAXN];
inline void read(int &x){
	char c;
	c=gc();
	while(c<'0'||c>'9'){
		c=gc();
	}
	while(c>='0'&&c<='9'){
		x=(x<<3)+(x<<1)+(c&15);
		c=gc();
	}
}
struct QUERY{
	int id,l,r;
}q[MAXN];
int answ[MAXN];
inline void write(int x){
	if(x<10){
		putchar(x|'0');
		return;
	}
	write(x/10);
	putchar(x%10|'0');
}
inline bool cmp(QUERY &H,QUERY &G){
	if(H.l/len!=G.l/len){
		return H.l/len<G.l/len;
	}
	if((H.l/len)&1){
		return H.r<G.r;
	}
	return H.r>G.r;
}
int main(){
	freopen("ring.in","r",stdin);
	freopen("ring.out","w",stdout);
	read(n);
	for(int i=1;i<=n;++i){
		read(a[i]);
		if(!iiidx[a[i]]){
			iiidx[a[i]]=++iidx;
		}
		a[i]=iiidx[a[i]];
	}
	read(Q);
	len=max(1,(int)(sqrt((double)(n)*n/(double)(Q))));
	for(int i=1;i<=Q;++i){
		read(q[i].l);read(q[i].r);
		q[i].id=i;
	}
	sort(q+1,q+Q+1,cmp);
	for(int k=1,i=0,j=1;k<=Q;++k){
		while(i<q[k].r){
			add(a[++i]);
		}
		while(i>q[k].r){
			del(a[i]),--i;
		}
		while(j<q[k].l){
			del(a[j]),++j;
		}
		while(j>q[k].l){
			add(a[--j]);
		}
		answ[q[k].id]=ans;
	}
	for(int k=1;k<=Q;++k){
		write(answ[k]);
		putchar('\n');
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}

最慢的点只有 $1.23\texttt{s}$。

这个故事告诉我们，时间是跟数组访问的跨度强相关的。这是一个 $2$ 倍常数的优化。