UVA13095 Tobby and Query 题解

分析

一眼莫队（虽然通过这题的范围显然看出出题人用的不是莫队）。

我们定义 \(\mathit{cnt}_{i}\) 表示数字 \(i\) 出现的次数。在指针的拓展增加 \(x\) 时，若有 \(\mathit{cnt}_{x}+1=1\)，则表示在在这个区间里，\(x\) 是第一次出现的，我们可以将答案加 \(1\)；在指针的收缩减去 \(x\) 时，若有 \(\mathit{cnt}_{x}-1=0\)，则表示在在这个区间里，\(x\) 将不会出现，我们可以将答案减 \(1\)。这样就能很容易地统计出某个区间内不同数字的数量啦。

注：这题多测，建议不要把没有必要开太大的数组开大，没必要清空的数组可以不清空。复杂度单组数据是 \(O(q\sqrt{n})\) 的，能过。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
#define x first
#define y second
#define re register
#define il inline
const int N=1e5+10,M=15;
int n,q,c[N];
struct node{
	int l,r,id;
}Q[N];
int len,cnt[M],ans,ANS[N];
il bool cmp(node a,node b){
	return ((a.l/len!=b.l/len)?(a.l<b.l):(((a.l/len)&1)?(a.r<b.r):(a.r>b.r)));
}
il void read(){
	for(re int i=1;i<=n;++i)
		scanf("%lld",&c[i]),cnt[c[i]]=0;
	scanf("%lld",&q);
	for(re int i=1;i<=q;++i)
		scanf("%lld%lld",&Q[i].l,&Q[i].r),Q[i].id=i;
	return ;
}
il void add(int x){
	++cnt[x];
	if(cnt[x]==1) ans++;
	return ;
}
il void del(int x){
	--cnt[x];
	if(cnt[x]==0) ans--;
	return ;
}
il void solve(){
	ans=0,len=sqrt(n),sort(Q+1,Q+q+1,cmp);
	int l=1,r=0;
	for(re int i=1;i<=q;++i){
		while(l>Q[i].l) add(c[--l]);
		while(r<Q[i].r) add(c[++r]);
		while(l<Q[i].l) del(c[l++]);
		while(r>Q[i].r) del(c[r--]);
		ANS[Q[i].id]=ans;
	}
	return ;
}
il void print(){
	for(re int i=1;i<=q;++i)
		printf("%lld\n",ANS[i]);
	return ;
}
signed main(){
	while(scanf("%lld",&n)==1){
		read(),solve(),print();
	}
	return 0;
}