Record

Judging $1$ 个小时了。。。

code

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,Q,a[N];//sq=sqrt n
int ans[N],vis[N],cnt,sq;
struct ne {
	int l,r,i;
	bool operator < (const ne &x) const {
		if(l/sq!=x.l/sq)	return l<x.l;
		if(l/sq &1)	return r<x.r;
		return r>x.r;
	}
}q[N];
inline void add(int p) {if(++vis[a[p]]==1)	++cnt;}
inline void del(int p) {if(--vis[a[p]]==0)	--cnt;}
signed main() {
	//ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n;	sq=sqrt(n);
	for(int i=1;i<=n;++i)	cin>>a[i];
	cin>>Q;
	for(int i=1;i<=Q;++i) {cin>>q[i].l>>q[i].r;q[i].i=i;}
	sort(q+1,q+Q+1);
	int l=1,r=0;
	for(int i=1;i<=Q;++i) {
		while(l>q[i].l)	add(--l);
		while(r<q[i].r)	add(++r);
		while(l<q[i].l)	del(l++);
		while(r>q[i].r)	del(r--);
		ans[q[i].i]=cnt;
	}
	for(int i=1;i<=Q;++i)	cout<<ans[i]<<endl;
	return 0;
}