关于查询区间最小没出现的自然数的cdq方法的可行性探讨

本文主要是介绍关于查询区间最小没出现的自然数的cdq方法的可行性探讨，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述这道题显然有一个可持久化线段树的做法。

首先我们意识到这个极广的值域没有什么用处。

我们首先想到必然存在一个 $\ x$ 使答案为 $\ x$ 或者 $\ [1,x-1]$ 中的最小的不存在的数字。

所以首先我们想到找到这个 $\ x$ 然后把没有必要的数字全部删掉，这样剩下的数字必然再 $\ [1,n]$ 中。

之后我们想到将 $a_{i}$ 在 $\ i$ 点存在转换为 $a_{i}$ 在 $\ [1,i-1],[i+1,n]$ 中不存在，设 $\ i$ 的两个值为 $\ q=i-1,w=i+1$ ，这样任意询问 $\ [l,r]$ 就是 $\ q \ge r$ 或者 $\ w \le l$ 的数字中的最小值。这显然是一个一维偏序问题，那么我们显然可以将每个询问看做两个，直接桶排序即可。复杂度 $\ O(n)$

实际上这种方法仅限于值的两两不同。

如果相同的值是存在的，那么我们依然可以将问题改变。显然如果同时存在两个值相同 $a_{i}=a_{j},i<j$ ，那么显然为 $a_{i}$ 在 $\ [1,i-1],[i+1,j-1],[j+1,n]$ 不存在，我们将其拆为三个操作， $q_{1}=1，w_{1}=i-1,q_{2}=i+1,w_{2}=j-1,q_{3}=j+1,w_{3}=n$ 。对于每个询问 $\ [l,r]$ ，即 $\ q \le l$ 且 $\ w \ge r$ 的最小值。那么我们先按照 $\ q$ 或者 $\ l$ 排序，cdq中按照 $\ r$ 或者 $\ w$ ，然后求解即可。 $O(n \log_{2}{n})$

#include<bits/stdc++.h>
using namespace std;
inline int read()
{char ch = getchar(); int x = 0;while (!isdigit(ch)) ch = getchar();while (isdigit(ch)){ x = x*10+ch-'0'; ch = getchar(); }return x;
}
int n,a[300300],b[300300],m,xxx,tot=0,head,tail,ans[200200];
struct nobe
{int op,l,r,w,id;
}q[600600],tmp[600600];
inline bool cmp(nobe a,nobe b)
{return (a.l^b.l) ? (a.l<b.l) : (a.op<b.op);
}
inline void cdq(int l,int r)
{if(l==r) return ;int mid=(l+r)>>1;cdq(l,mid);cdq(mid+1,r);int i=l,j=mid+1,ccnt=0,sum=999999999;while(j<=r){while((q[i].r>=q[j].r)&&(i<=mid)){tmp[++ccnt]=q[i];if(q[i].op&1){sum=min(sum,q[i].w);}++i;}tmp[++ccnt]=q[j];if(q[j].op^1){ans[q[j].id]=min(ans[q[j].id],sum);}++j;}while(i<=mid){tmp[++ccnt]=q[i];++i;}i=1;while(i<=ccnt){q[l+i-1]=tmp[i];++i;}
}
int main()
{memset(b,0,sizeof(b));n=read();m=read();int i=1;while(i<=n){a[i]=read();if(a[i]<=n) ++b[a[i]];++i;}i=-1;while(i<=n){if(b[i+1]) ++i;else break;}xxx=i+1;i=0;while(i<xxx){b[i]=0;++i;}i=1;while(i<=n){if(a[i]<xxx){if((i^1)&&(b[a[i]]^i-1)){q[++tot]=(nobe){1,b[a[i]]+1,i-1,a[i],0};}b[a[i]]=i;}++i;}i=0;while(i<xxx){if(b[i]^n) q[++tot]=(nobe){1,b[i]+1,n,i,0};++i;}i=1;while(i<=m){int l,r;l=read();r=read();ans[i]=xxx;q[++tot]=(nobe){2,l,r,0,i};++i; }sort(q+1,q+tot+1,cmp);cdq(1,tot);i=1;while(i<=m){printf("%d\n",ans[i]);++i;}return 0;
}