悬关。

record

#3 本地（CPU: Intel(R) Xeon(R) CPU E5-26xx series @2.10 GHz）跑了约 6.6s。

#include<bits/stdc++.h>
// #pragma G++ optimize(2)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
#define fi first
#define se second
const int N=1e6+5;
int a[N];
struct Query {
	int id,l,r;
} que[N];
int cnt[N],pos[N],ans[N];
bool cmp(Query A,Query B) {
	if(pos[A.l]!=pos[B.l]) return pos[A.l]<pos[B.l];
	if(pos[A.l]&1) return A.l<B.l;
	else return A.l>B.l;
}
int curans=0;
void add(int x) {
	cnt[a[x]]++;
	if(cnt[a[x]]==1) curans++;
}
void del(int x) {
	cnt[a[x]]--;
	if(cnt[a[x]]==0) curans--;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int beginTime=clock();
	int n;cin>>n;
	int block=sqrt(n);
	for(int i=1;i<=n;i++) {
		cin>>a[i];
		pos[i]=(i-1)/block+1;
	}
	int m;cin>>m;
	for(int i=1;i<=m;i++) {
		que[i].id=i;
		cin>>que[i].l>>que[i].r;
	}
	sort(que+1,que+m+1,cmp);
	int l=1,r=0;
	for(int i=1;i<=m;i++) {
		while(l<que[i].l) del(l++);
		while(r>que[i].r) del(r--);
		while(l>que[i].l) add(--l);
		while(r<que[i].r) add(++r);
		ans[que[i].id]=curans;
	}
	for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';
	int endTime=clock();
	cerr<<"Time: "<<endTime-beginTime<<'\n';
	return 0;
}