题解 P4137 【Rmq Problem / mex】

Great_Influence

2018-06-21 20:07:47

Solution

我觉得在线算法不可爱,所以写了离线算法。 假如我们要求的区间左端点在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; } ```