首页 > 代码库 > HH的项链
HH的项链
基本上每个网站上都有，就不粘提面啦。
这道题要求维护区间种类数，不支持区间加减法。
所以需要通过转换使其满足树状数组/线段树的条件。
首先，对于段区间中的数，若有数重复出现，则只需关心最后出现的一个。
所以，我们可以对所有查询区间的r非降排序，从左向右推now_r并同时维护一个树状数组。
树状数组表示一段区间数的种类数，具体看一个栗子：
1,2,1,3
当now_r=1，insert（1,1）表示在位置1出现了一个未重复的数，需要在树状数组上对应的位置+1，此时树状数组对应序列每个位置上的值为：1 0 0 0
当now_r=2，insert（2,1）：1 1 0 0
当now_r=1，由于数a[3]（就是1）之前出现过，最后一遍出现的地方为1，则insert（1，-1），insert（3,1），即减去之前位置加上的种类数转而在右边的位置+1，：0 1 1 0
当now_r=3，insert（4,1）：0 1 1 1
这样，每次i更新时看是否i=一个r，while输出sum[l,r]=sum[r]-sum[l-1]（询问[2,3]=sum[3]-sum[2-1]=2）
最后一点，为了记录每个数最后一遍出现过的位置，需要一个last数组。last[i]=0表示数i还未出现过，last[i]=k表示数i最后一次出现的位置为k。
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 using namespace std; 5 const int maxn=1000001,N=50001,M=200001; 6 int last[maxn],sum[N],a[N],ans[M],n; 7 struct fx{ 8 int l,r,num; 9 }q[M];10 bool cmp(fx a,fx b){11 return a.r<b.r;12 }13 int query(int),lowbit(int);14 void insert(int,int);15 int main(){16 int m,nowques,tmp;17 memset(last,0,sizeof(last));18 scanf("%d",&n);19 for (int i=1;i<=n;i++)20 scanf("%d",&a[i]);21 scanf("%d",&m);22 for (int i=1;i<=m;i++){23 scanf("%d %d",&q[i].l,&q[i].r);24 q[i].num=i;25 }26 sort(q+1,q+m+1,cmp);27 nowques=1;28 for (int i=1;i<=n;i++){29 insert(i,1);30 if (last[a[i]]) insert(last[a[i]],-1);31 last[a[i]]=i;32 tmp=query(i);33 while (q[nowques].r==i&&nowques<=m){34 ans[q[nowques].num]=tmp-query(q[nowques].l-1);35 nowques++;36 }37 }38 for (int i=1;i<=m;i++)39 printf("%d\n",ans[i]);40 }41 int query(int x){42 int s=0;43 for (int i=x;i;i-=lowbit(i))44 s+=sum[i];45 return s;46 }47 void insert(int x,int v){48 for (int i=x;i<=n;i+=lowbit(i))49 sum[i]+=v;50 }51 int lowbit(int x){52 return x&(-x);53 }
HH的项链
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。