题目大意:
一个长度为 \(n\) 的序列,第 \(i\) 个数为 \(a_i\),求 \(L\) 和 \(R\) 之间有多少个不同的 \(a_i\) 。
\(1 \le n,m,a_i \le 10^6\)
题解:
又是一个比较有趣的trick。以下部分借鉴于网络。
注意到对于同一区间的一个数,我们可以只关心最后出现的位置。
有一个方法是我们维护每个位置出现的数是否最后一次出现。于是,求前缀和便可知\([1..n]\) 的不同数的个数了。
回到本题,对于每个 \(r_i\) ,我们可以维护 \([1..r_i]\) 时的不同数及此时 \([1..l_i]\)的不同数(注意前面的区间会随着后面数的加入而改变)。考虑到本题不强制在线,这可以通过离线实现。
#include<bits/stdc++.h>
#define lowbit(x) x&(-x)
#define N 1001000
using namespace std;
int vis[N],t[N];
int n,a[N],m;
struct data
{
int L,R,num,ans;
}q[N];
bool cmp(data x,data y)
{
return x.R<y.R;
}
bool cnp(data x,data y)
{
return x.num<y.num;
}
void add(int x,int y)
{
for (int i=x;i<=n;i+=lowbit(i))
t[i]+=y;
}
int ask(int x)
{
int ans=0;
for (int i=x;i;i-=lowbit(i))
ans+=t[i];
return ans;
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
scanf("%d",&m);
for (int i=1;i<=m;i++)
{
scanf("%d%d",&q[i].L,&q[i].R);
q[i].num=i;
}
sort(q+1,q+m+1,cmp);
for (int i=1,j=1;i<=n;i++)
{
if (vis[a[i]]) add(vis[a[i]],-1);
add(i,1);vis[a[i]]=i;
while (i==q[j].R) q[j].ans=ask(q[j].R)-ask(q[j].L-1),j++;
}
sort(q+1,q+m+1,cnp);
for (int i=1;i<=m;i++)
{
cout<<q[i].ans<<endl;
}
return 0;
}