Bzoj 3339: Rmq Problem && Bzoj 3585: mex 莫队,树状数组,二分

3339: Rmq Problem

Time Limit: 20 Sec Memory Limit: 128 MB
Submit: 833 Solved: 397
[Submit][Status][Discuss]

Description

Input

Output

Sample Input

7 5
0 2 1 0 1 3 2
1 3
2 3
1 4
3 6
2 7

Sample Output

3
0
3
2
4

HINT

Source

By Xhr

[Submit][Status][Discuss]

题解：

3585和3339貌似除了范围不一样，好像重了。。。

但是我想了一种只能过3339的方法。。。(3585也可以过的>_<，具体往下看！！！)

＊增加：因为我们询问的区间在1～n内，所以权值大于n的一定不是mex,所以不用修改，直接跳过。(可以在纸上画画)＊

*于是就可以A两道了～～～*

莫队＋树状数组＋二分。。。

莫队和树状数组是毫无疑问要用的。。。

但是二分呢？？？

我们考虑如何能算一个原序列的mex？？？

就是对于一个区间，我们用树状数组来维护其中出现过的元素。出现过的标记为1，没有的标记为0。若一个区间内的1的个数等于区间的长度，则mex一定不存在于此区间内。若1的个数小于区间长度，则一定存在于此区间内。

例如：

0 1 2 3

— —— > 代表0，2，3被选了

1 0 1 1 ---> 把存在的标记为1。

—— > 二分的前一半和为1，但长度为2，所以一定存在mex。

剩余的继续二分。（程序下面还有东西的！！！）

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define MAXN 200010
  4 struct node
  5 {
  6     int l,r,id;
  7 }q[MAXN];
  8 int tot,BIT[MAXN],color[MAXN],sz[MAXN],pos[MAXN],ans[MAXN],gs[MAXN];
  9 int read()
 10 {
 11     int s=0,fh=1;char ch=getchar();
 12     while(ch<'0'||ch>'9'){if(ch=='-')fh=-1;ch=getchar();}
 13     while(ch>='0'&&ch<='9'){s=s*10+(ch-'0');ch=getchar();}
 14     return s*fh;
 15 }
 16 bool cmp(node aa,node bb)
 17 {
 18     if(pos[aa.l]==pos[bb.l])return aa.r<bb.r;
 19     return aa.l<bb.l;
 20 }
 21 int Lowbit(int o){return o&(-o);}
 22 void Update(int o,int o1)
 23 {
 24     while(o<=tot)
 25     {
 26         BIT[o]+=o1;
 27         o+=Lowbit(o);
 28     }
 29 }
 30 int Sum(int o)
 31 {
 32     int sum=0;
 33     while(o>0)
 34     {
 35         sum+=BIT[o];
 36         o-=Lowbit(o);
 37     }
 38     return sum;
 39 }
 40 int getans(int L,int R)
 41 {
 42     int mid,wz;
 43     if(Sum(R)-Sum(L-1)==(L-R+1))return R+1;
 44     while(L<=R)
 45     {
 46         int mid=(L+R)/2;
 47         if((Sum(mid)-Sum(L-1))<(mid-L+1))wz=mid,R=mid-1;
 48         else L=mid+1;
 49     }
 50     return wz;
 51 }
 52 int main()
 53 {
 54     int n,m,block,i,L,R,wz;
 55     n=read();m=read();
 56     block=(int)sqrt(n);
 57     for(i=1;i<=n;i++)color[i]=read(),sz[i]=color[i];
 58     sort(sz+1,sz+n+1);
 59     tot=unique(sz+1,sz+n+1)-(sz+1);
 60     for(i=1;i<=m;i++)q[i].l=read(),q[i].r=read(),q[i].id=i;
 61     for(i=1;i<=n;i++)pos[i]=(int)(i-1)/block+1,color[i]++;
 62     sort(q+1,q+m+1,cmp);
 63     L=1;R=0;
 64     memset(gs,0,sizeof(gs));
 65     for(i=1;i<=m;i++)
 66     {
 67         while(L<q[i].l)
 68         {
 69             //wz=lower_bound(sz+1,sz+tot+1,color[L])-sz;
 70             wz=color[L];
 71             gs[wz]--;
 72             if(gs[wz]==0)Update(wz,-1);
 73             L++;
 74         }
 75         while(L>q[i].l)
 76         {
 77             L--;
 78             //wz=lower_bound(sz+1,sz+tot+1,color[L])-sz;
 79             wz=color[L];
 80             gs[wz]++;
 81             if(gs[wz]==1)Update(wz,1);
 82         }
 83         while(R<q[i].r)
 84         {
 85             R++;
 86             //wz=lower_bound(sz+1,sz+tot+1,color[R])-sz;
 87             wz=color[R];
 88             gs[wz]++;
 89             if(gs[wz]==1)Update(wz,1);
 90         }
 91         while(R>q[i].r)
 92         {
 93             //wz=lower_bound(sz+1,sz+tot+1,color[R])-sz;
 94             wz=color[R];
 95             gs[wz]--;
 96             if(gs[wz]==0)Update(wz,-1);
 97             R--;
 98         }
 99         ans[q[i].id]=getans(1,n+1);
100     }
101     for(i=1;i<=m;i++)printf("%d
",ans[i]-1);
102     fclose(stdin);
103     fclose(stdout);
104     return 0;
105 }

两道题都可以过的程序：

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define MAXN 200010
  4 struct node
  5 {
  6     int l,r,id;
  7 }q[MAXN];
  8 int tot,BIT[MAXN],color[MAXN],sz[MAXN],pos[MAXN],ans[MAXN],gs[MAXN];
  9 int read()
 10 {
 11     int s=0,fh=1;char ch=getchar();
 12     while(ch<'0'||ch>'9'){if(ch=='-')fh=-1;ch=getchar();}
 13     while(ch>='0'&&ch<='9'){s=s*10+(ch-'0');ch=getchar();}
 14     return s*fh;
 15 }
 16 bool cmp(node aa,node bb)
 17 {
 18     if(pos[aa.l]==pos[bb.l])return aa.r<bb.r;
 19     return aa.l<bb.l;
 20 }
 21 int Lowbit(int o){return o&(-o);}
 22 void Update(int o,int o1)
 23 {
 24     while(o<=tot)
 25     {
 26         BIT[o]+=o1;
 27         o+=Lowbit(o);
 28     }
 29 }
 30 int Sum(int o)
 31 {
 32     int sum=0;
 33     while(o>0)
 34     {
 35         sum+=BIT[o];
 36         o-=Lowbit(o);
 37     }
 38     return sum;
 39 }
 40 int getans(int L,int R)
 41 {
 42     int mid,wz;
 43     if(Sum(R)-Sum(L-1)==(L-R+1))return R+1;
 44     while(L<=R)
 45     {
 46         int mid=(L+R)/2;
 47         if((Sum(mid)-Sum(L-1))<(mid-L+1))wz=mid,R=mid-1;
 48         else L=mid+1;
 49     }
 50     return wz;
 51 }
 52 int main()
 53 {
 54     int n,m,block,i,L,R,wz;
 55     n=read();m=read();
 56     block=(int)sqrt(n);
 57     for(i=1;i<=n;i++)color[i]=read(),sz[i]=color[i];
 58     sort(sz+1,sz+n+1);
 59     tot=unique(sz+1,sz+n+1)-(sz+1);
 60     for(i=1;i<=m;i++)q[i].l=read(),q[i].r=read(),q[i].id=i;
 61     for(i=1;i<=n;i++)pos[i]=(int)(i-1)/block+1,color[i]++;
 62     sort(q+1,q+m+1,cmp);
 63     L=1;R=0;
 64     memset(gs,0,sizeof(gs));
 65     for(i=1;i<=m;i++)
 66     {
 67         while(L<q[i].l)
 68         {
 69             //wz=lower_bound(sz+1,sz+tot+1,color[L])-sz;
 70             wz=color[L];
 71             if(wz<=n+1)//加这一句就可以过了！！！
 72             {
 73                 gs[wz]--;
 74                 if(gs[wz]==0)Update(wz,-1);
 75             }
 76             L++;
 77         }
 78         while(L>q[i].l)
 79         {
 80             L--;
 81             //wz=lower_bound(sz+1,sz+tot+1,color[L])-sz;
 82             wz=color[L];
 83             if(wz<=n+1)
 84             {
 85                 gs[wz]++;
 86                 if(gs[wz]==1)Update(wz,1);
 87             }
 88         }
 89         while(R<q[i].r)
 90         {
 91             R++;
 92             //wz=lower_bound(sz+1,sz+tot+1,color[R])-sz;
 93             wz=color[R];
 94             if(wz<=n+1)
 95             {
 96                 gs[wz]++;
 97                 if(gs[wz]==1)Update(wz,1);
 98             }
 99         }
100         while(R>q[i].r)
101         {
102             //wz=lower_bound(sz+1,sz+tot+1,color[R])-sz;
103             wz=color[R];
104             if(wz<=n+1)
105             {
106                 gs[wz]--;
107                 if(gs[wz]==0)Update(wz,-1);
108             }
109             R--;
110         }
111         ans[q[i].id]=getans(1,n+1);
112     }
113     for(i=1;i<=m;i++)printf("%d
",ans[i]-1);
114     fclose(stdin);
115     fclose(stdout);
116     return 0;
117 }