题解 P4137 【Rmq Problem / mex】
Great_Influence
2018-06-21 20:07:47
我觉得在线算法不可爱,所以写了离线算法。
假如我们要求的区间左端点在1,则我们可以转换问题:
对于每个数字,给它附上它第一次出现的位置的权值。
那么,答案就是:
求最大的数$t$,使得$\max\limits_{i=0}^{t-1} p[i]\le r$
$p[i]$就是$i$这个数的权值。
这个可以用二分简单求出。
然后就是左端点不固定的情况。加入我们要将做短点右移一位,如果我们求出了这个位置上的数下一次出现的位置,我们可以将这个数第一次出现的位置改到下一次出现的位置。
那么,我们只需要预处理每个数初次出现位置和下一次出现位置,然后支持单点修改和区间查询最大值就可以了。我们选择了线段树。
如果每次二分后直接在线段树上查询,则该算法是$O(n+qlog^2n)$的。然而可以直接在线段树上二分,时间复杂度变为$O(n+qlogn)$。(所以也可以当作线段树二分的模板题)
代码:
```cpp
#include<bits/stdc++.h>
#define For(i,a,b) for(i=(a),i##end=(b);i<=i##end;++i)
#define Forward(i,a,b) for(i=(a),i##end=(b);i>=i##end;--i)
#define Rep(i,a,b) for(register uint32 i=(a),i##end=(b);i<=i##end;++i)
#define Repe(i,a,b) for(register uint32 i=(a),i##end=(b);i>=i##end;--i)
#define Chkmax(a,b) a=a>b?a:b
#define Chkmin(a,b) a=a<b?a:b
#define pb push_back
using uint32=unsigned int;
using uint64=unsigned long long;
using namespace std;
template<typename T>inline void read(T &x){
T s=0,f=1;char k=getchar();
while(!isdigit(k)&&k^'-')k=getchar();
if(!isdigit(k)){f=-1;k=getchar();}
while(isdigit(k)){s=s*10+(k^48);k=getchar();}
x=s*f;
}
template<typename T>inline void write(T x,char ed='\n')
{
static int sta[111],tp;
if(!x){putchar('0'),putchar(ed);return;}
for(tp=0;x;x/=10)sta[++tp]=x%10;
for(;tp;putchar(sta[tp--]^48));
putchar(ed);
}
void file(void){
#ifndef ONLINE_JUDGE
freopen("water.in","r",stdin);
freopen("water.out","w",stdout);
#endif
}
const uint32 MAXN=2e5+7;
static uint32 n,m,w[MAXN];
static uint32 fp[MAXN],nxt[MAXN];
namespace Segment_Tree
{
static uint32 p[MAXN<<2];
void modif(uint32 h,uint32 l,uint32 r,uint32 x,uint32 z)
{
if(l==r)
{
p[h]=z;
return;
}
static uint32 mid;mid=(l+r)>>1;
x<=mid?modif(h<<1,l,mid,x,z):modif(h<<1|1,mid+1,r,x,z);
p[h]=max(p[h<<1],p[h<<1|1]);
}
inline uint32 query(int x,int y)
{
static uint32 h,l,r,mid,mx;mx=0;h=l=1;r=n;
while(l<r)
{
mid=(l+r)>>1;
if(y-x+1>=mid && max(p[h<<1],mx)<=y)
Chkmax(mx,p[h<<1]),h=h<<1|1,l=mid+1;
else h<<=1,r=mid;
}
return l-1;
}
}
using namespace Segment_Tree;
static struct quer
{
int l,r,id;
friend bool operator<(quer a,quer b){return a.l<b.l;}
}q[MAXN];
inline void init()
{
read(n);read(m);
memset(p,0x3f,sizeof p);
Rep(i,1,n)
{
read(w[i]);++w[i];
if(w[i]<=n)
{
if(fp[w[i]])nxt[fp[w[i]]]=i;
else modif(1,1,n,w[i],i);
fp[w[i]]=i;
}
}
Rep(i,1,m)read(q[i].l),read(q[i].r),q[i].id=i;
}
static uint32 ans[MAXN];
inline void solve()
{
sort(q+1,q+m+1);
static uint32 ps=0;
w[0]=1e9;
Rep(i,1,m)
{
for(;ps<q[i].l;++ps)if(w[ps]<=n)
modif(1,1,n,w[ps],nxt[ps]?nxt[ps]:p[0]);
ans[q[i].id]=query(q[i].l,q[i].r);
}
Rep(i,1,m)printf("%u\n",ans[i]);
}
int main(void)
{
file();
init();
solve();
return 0;
}
```