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
0 2 1 0 1 3 2
1 3
2 3
1 4
3 6
2 7
Sample Output
3
0
3
2
4
0
3
2
4
HINT
Source
题解：
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。
剩余的继续二分。（程序下面还有东西的！！！）
#include<bits/stdc++.h>
using namespace std;
#define MAXN 200010
struct node
{
int l,r,id;
}q[MAXN];
int tot,BIT[MAXN],color[MAXN],sz[MAXN],pos[MAXN],ans[MAXN],gs[MAXN];
int read()
{
int s=,fh=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')fh=-;ch=getchar();}
while(ch>=''&&ch<=''){s=s*+(ch-'');ch=getchar();}
return s*fh;
}
bool cmp(node aa,node bb)
{
if(pos[aa.l]==pos[bb.l])return aa.r<bb.r;
return aa.l<bb.l;
}
int Lowbit(int o){return o&(-o);}
void Update(int o,int o1)
{
while(o<=tot)
{
BIT[o]+=o1;
o+=Lowbit(o);
}
}
int Sum(int o)
{
int sum=;
while(o>)
{
sum+=BIT[o];
o-=Lowbit(o);
}
return sum;
}
int getans(int L,int R)
{
int mid,wz;
if(Sum(R)-Sum(L-)==(L-R+))return R+;
while(L<=R)
{
int mid=(L+R)/;
if((Sum(mid)-Sum(L-))<(mid-L+))wz=mid,R=mid-;
else L=mid+;
}
return wz;
}
int main()
{
int n,m,block,i,L,R,wz;
n=read();m=read();
block=(int)sqrt(n);
for(i=;i<=n;i++)color[i]=read(),sz[i]=color[i];
sort(sz+,sz+n+);
tot=unique(sz+,sz+n+)-(sz+);
for(i=;i<=m;i++)q[i].l=read(),q[i].r=read(),q[i].id=i;
for(i=;i<=n;i++)pos[i]=(int)(i-)/block+,color[i]++;
sort(q+,q+m+,cmp);
L=;R=;
memset(gs,,sizeof(gs));
for(i=;i<=m;i++)
{
while(L<q[i].l)
{
//wz=lower_bound(sz+1,sz+tot+1,color[L])-sz;
wz=color[L];
gs[wz]--;
if(gs[wz]==)Update(wz,-);
L++;
}
while(L>q[i].l)
{
L--;
//wz=lower_bound(sz+1,sz+tot+1,color[L])-sz;
wz=color[L];
gs[wz]++;
if(gs[wz]==)Update(wz,);
}
while(R<q[i].r)
{
R++;
//wz=lower_bound(sz+1,sz+tot+1,color[R])-sz;
wz=color[R];
gs[wz]++;
if(gs[wz]==)Update(wz,);
}
while(R>q[i].r)
{
//wz=lower_bound(sz+1,sz+tot+1,color[R])-sz;
wz=color[R];
gs[wz]--;
if(gs[wz]==)Update(wz,-);
R--;
}
ans[q[i].id]=getans(,n+);
}
for(i=;i<=m;i++)printf("%d\n",ans[i]-);
fclose(stdin);
fclose(stdout);
return ;
}
两道题都可以过的程序：
#include<bits/stdc++.h>
using namespace std;
#define MAXN 200010
struct node
{
int l,r,id;
}q[MAXN];
int tot,BIT[MAXN],color[MAXN],sz[MAXN],pos[MAXN],ans[MAXN],gs[MAXN];
int read()
{
int s=,fh=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')fh=-;ch=getchar();}
while(ch>=''&&ch<=''){s=s*+(ch-'');ch=getchar();}
return s*fh;
}
bool cmp(node aa,node bb)
{
if(pos[aa.l]==pos[bb.l])return aa.r<bb.r;
return aa.l<bb.l;
}
int Lowbit(int o){return o&(-o);}
void Update(int o,int o1)
{
while(o<=tot)
{
BIT[o]+=o1;
o+=Lowbit(o);
}
}
int Sum(int o)
{
int sum=;
while(o>)
{
sum+=BIT[o];
o-=Lowbit(o);
}
return sum;
}
int getans(int L,int R)
{
int mid,wz;
if(Sum(R)-Sum(L-)==(L-R+))return R+;
while(L<=R)
{
int mid=(L+R)/;
if((Sum(mid)-Sum(L-))<(mid-L+))wz=mid,R=mid-;
else L=mid+;
}
return wz;
}
int main()
{
int n,m,block,i,L,R,wz;
n=read();m=read();
block=(int)sqrt(n);
for(i=;i<=n;i++)color[i]=read(),sz[i]=color[i];
sort(sz+,sz+n+);
tot=unique(sz+,sz+n+)-(sz+);
for(i=;i<=m;i++)q[i].l=read(),q[i].r=read(),q[i].id=i;
for(i=;i<=n;i++)pos[i]=(int)(i-)/block+,color[i]++;
sort(q+,q+m+,cmp);
L=;R=;
memset(gs,,sizeof(gs));
for(i=;i<=m;i++)
{
while(L<q[i].l)
{
//wz=lower_bound(sz+1,sz+tot+1,color[L])-sz;
wz=color[L];
if(wz<=n+)//加这一句就可以过了！！！
{
gs[wz]--;
if(gs[wz]==)Update(wz,-);
}
L++;
}
while(L>q[i].l)
{
L--;
//wz=lower_bound(sz+1,sz+tot+1,color[L])-sz;
wz=color[L];
if(wz<=n+)
{
gs[wz]++;
if(gs[wz]==)Update(wz,);
}
}
while(R<q[i].r)
{
R++;
//wz=lower_bound(sz+1,sz+tot+1,color[R])-sz;
wz=color[R];
if(wz<=n+)
{
gs[wz]++;
if(gs[wz]==)Update(wz,);
}
}
while(R>q[i].r)
{
//wz=lower_bound(sz+1,sz+tot+1,color[R])-sz;
wz=color[R];
if(wz<=n+)
{
gs[wz]--;
if(gs[wz]==)Update(wz,-);
}
R--;
}
ans[q[i].id]=getans(,n+);
}
for(i=;i<=m;i++)printf("%d\n",ans[i]-);
fclose(stdin);
fclose(stdout);
return ;
}