[关闭]
@zzzc18 2017-12-25T08:42:23.000000Z 字数 2892 阅读 469

BZOJ1878: [SDOI2009]HH的项链

bzoj BIT 线段树


Description

HH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运,所以每次散步 完后,他都会随意取出一
段贝壳,思考它们所表达的含义。HH不断地收集新的贝壳,因此他的项链变得越来越长。有一天,他突然提出了一
个问题:某一段贝壳中,包含了多少种不同的贝壳?这个问题很难回答。。。因为项链实在是太长了。于是,他只
好求助睿智的你,来解决这个问题。

Input

第一行:一个整数 ,表示项链的长度。
第二行: 个整数,表示依次表示项链中贝壳的编号(编号为 之间的整数)。
第三行:一个整数 ,表示HH询问的个数。
接下来 行:每行两个整数,),表示询问的区间。

Output

行,每行一个整数,依次表示询问对应的答案。


Soulution:

SOL_1

离线处理,可以将问题进行转化。
先按照询问的右端点排序,于是我们可以对每个右端点依次回答以下问题:

从序列中一个位置到最后,有多少种颜色

这时,我们可以将该段原序列的前缀(即从头到固定的右端点)中每种颜色最后的位置赋为 ,该颜色之前出现的位置赋为 ,计算前缀和 以及 ,相减就是出现的颜色数,用树状数组维护即可。

具体操作:
1.按右端点排序
2.对于当前所到点 用树状数组将 处加 ,在 (前一个出现位置)处减
3.回答所有右端点与 相同的询问

总复杂度

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. using namespace std;
  5. const int MAXN = 200000+9;
  6. const int SIZE = 1000000+9;
  7. int tree[MAXN];
  8. int head[SIZE];
  9. int next[MAXN];
  10. int num[MAXN];
  11. int n,m;
  12. struct Q{
  13. int l,r,id,val;
  14. }ask[MAXN];
  15. bool cmp(const Q &A,const Q &B){
  16. return A.r==B.r?A.l<B.l:A.r<B.r;
  17. }
  18. bool back(const Q &A,const Q &B){
  19. return A.id<B.id;
  20. }
  21. int lowbit(int x){
  22. return x&-x;
  23. }
  24. void add(int pos,int val){
  25. if(pos==0)return;
  26. for(int i=pos;i<=n;i+=lowbit(i))
  27. tree[i]+=val;
  28. }
  29. int getsum(int pos){
  30. int re=0;
  31. for(int i=pos;i;i-=lowbit(i))
  32. re+=tree[i];
  33. return re;
  34. }
  35. void solve(){
  36. sort(ask+1,ask+m+1,cmp);
  37. int now=1;
  38. for(int i=1;i<=n;i++){
  39. add(next[i],-1);
  40. add(i,1);
  41. while(ask[now].r==i && now<=m){
  42. ask[now].val=getsum(ask[now].r)-getsum(ask[now].l-1);
  43. now++;
  44. }
  45. }
  46. sort(ask+1,ask+m+1,back);
  47. for(int i=1;i<=m;i++){
  48. printf("%d",ask[i].val);
  49. if(i!=m)putchar('\n');
  50. }
  51. }
  52. int main(){
  53. scanf("%d",&n);
  54. for(int i=1;i<=n;i++){
  55. scanf("%d",num+i);
  56. next[i]=head[num[i]];
  57. head[num[i]]=i;
  58. }
  59. scanf("%d",&m);
  60. for(int i=1;i<=m;i++){
  61. scanf("%d%d",&ask[i].l,&ask[i].r);
  62. ask[i].id=i;
  63. }
  64. solve();
  65. return 0;
  66. }

SOL_2

在线算法
使用主席树,计算当前询问区间 有多少点的 (同样是前一次出现的位置) 要小于 这就是最终的答案。
感觉这个不用怎么解释,这样做可以计算颜色并且不重复,总复杂度同样是

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. using namespace std;
  5. const int MAXN = 50000+9;
  6. const int RANGE = 1000000;
  7. const int SIZE = 1500000;
  8. int n,m;
  9. int num[MAXN];
  10. struct T{
  11. int ls,rs;
  12. int sum;
  13. }tree[SIZE];
  14. int rt[MAXN];
  15. int head[RANGE+9];
  16. int pred[MAXN];
  17. int cnt;
  18. int insert(int pre,int left_range,int right_range,int pos){
  19. int now=++cnt;
  20. tree[now]=tree[pre];
  21. tree[now].sum++;
  22. if(left_range==right_range)
  23. return now;
  24. int mid=left_range+right_range>>1;
  25. if(pos<=mid)tree[now].ls=insert(tree[pre].ls,left_range,mid,pos);
  26. else tree[now].rs=insert(tree[pre].rs,mid+1,right_range,pos);
  27. return now;
  28. }
  29. int query(int pre,int now,int left_range,int right_range,int pos){
  30. if(left_range==right_range){
  31. return tree[now].sum-tree[pre].sum;
  32. }
  33. int mid=left_range+right_range>>1;
  34. if(pos<=mid)return query(tree[pre].ls,tree[now].ls,left_range,mid,pos);
  35. else return tree[tree[now].ls].sum-tree[tree[pre].ls].sum+
  36. query(tree[pre].rs,tree[now].rs,mid+1,right_range,pos);
  37. }
  38. int main(){
  39. scanf("%d",&n);
  40. for(int i=1;i<=n;i++){
  41. scanf("%d",&num[i]);
  42. pred[i]=head[num[i]];
  43. head[num[i]]=i;
  44. }
  45. for(int i=1;i<=n;i++)
  46. rt[i]=insert(rt[i-1],0,RANGE,pred[i]);
  47. scanf("%d",&m);
  48. for(int i=1;i<=m;i++){
  49. int l,r;
  50. scanf("%d%d",&l,&r);
  51. printf("%d\n",query(rt[l-1],rt[r],0,RANGE,l-1));
  52. }
  53. return 0;
  54. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注