这真是个憨憨。

所以到底怎么做？为什么无论是莫队还是树状数组都会超时？ （莫队(O2)超时两个，树状数组re 1 tle 1）

树状数组

#include<bits/stdc++.h>
#define ll long long
const ll N=2000010;
using namespace std;
int n,m,a[N],last[N],ans[N];
struct query
{
	int l,r,id;
}q[N];
bool cmp(query x,query y)
{
	if(x.r>y.r) return false;
	return true;
}
inline int read()
{
	int num=0,flag=1;
	char c=getchar();
	while(c<'0'||c>'9') {if(c=='-')flag=-1;c=getchar();}
	while(c>='0'&&c<='9'){num=num*10+c-'0';c=getchar();}
	return num*flag;
}
struct FenwickTree
{
	int c[N];
	int lowbit(int n){return n&(-n);} 
	void update(int pos,int d)
	{
		while(pos<=n)
		{
			c[pos]+=d;
			pos+=lowbit(pos);
		}
	}
	int sum(int pos)
	{
		int res=0;
		while(pos)
		{
			res+=c[pos];
			pos-=lowbit(pos);
		}
		return res;
	}
}t;
int main()
{
	n=read();
	for(int i=1;i<=n;i++)
		a[i]=read();
	m=read();int r1,r2;
	for(int i=1;i<=m;i++)
	{
		r1=read(); r2=read();
		q[i].l=r1;q[i].r=r2;q[i].id=i;
	}
	sort(q+1,q+m+1,cmp);
	int qr=1;
	for(int i=1;i<=m;i++)
	{
		while(qr<=q[i].r)
		{
			if(last[a[qr]]!=0)t.update(last[a[qr]],-1);
			t.update(qr,1);last[a[qr]]=qr;qr++;
		}
		ans[q[i].id]=t.sum(q[i].r)-t.sum(q[i].l-1);
	}
	for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}

莫队

#include <bits/stdc++.h>
#define N 1010000
using namespace std;
int a[N], cnt[N],belong[N];
int n,m,size,sum,now,ans[N];
struct query 
{
	int l,r,id;
}q[N];
inline int read()
{
	int num=0,flag=1;
	char c=getchar();
	while(c>'9'||c<'0') {if(c=='-')flag=-1;c=getchar();}
	while(c>='0'&&c<='9'){num=num*10+c-'0';c=getchar();}
	return num*flag;
}
inline void print(int x) 
{
	if(x/10)print(x/10);
	putchar(x%10+'0');
}
inline bool cmp(query a, query b)
{
	return (belong[a.l]^belong[b.l])?belong[a.l]<belong[b.l]:((belong[a.l]&1)?a.r<b.r:a.r>b.r);
}
inline void work()
{
	sort(q+1,q+m+1,cmp);
	int l=1,r=0;
	for(int i=1;i<=m;++i)
	{
		int ql=q[i].l,qr=q[i].r;
		while(l<ql)now-=!--cnt[a[l++]];//!0=1,!1=!2=!x(x≠0)=0 
		while(l>ql)now+=!cnt[a[--l]]++;
		while(r<qr)now+=!cnt[a[++r]]++;
		while(r>qr)now-=!--cnt[a[r--]];
		ans[q[i].id]=now;
	}
}
int main() 
{
	n=read();
	size=sqrt(n);
	sum=ceil((double)n/size);
	for(int i=1;i<=sum;++i) 
		for(int j=(i-1)*size+1;j<=i*size;++j)
			belong[j]=i;
	for(int i=1;i<=n;++i)a[i]=read(); 
	m=read();
	for(int i=1;i<=m;++i)
	{
		q[i].l=read(),q[i].r=read();
		q[i].id=i;
	}
	work();
	for(int i=1;i<=m;++i)print(ans[i]),putchar('\n');
	return 0;
}