题目链接
题目大意:
一个长度为 \(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; }