题目描述
有一个长度为n的数组{a1,a2,…,an}。m次询问，每次询问一个区间内最小没有出现过的自然数。
输入格式
第一行n,m。
第二行为n个数。
从第三行开始，每行一个询问l,r。
输出格式
一行一个数，表示每个询问的答案。
一开始以为像答案这样的做法会超时，没想到真是这样写。。。
#include<cstdio>
#include<algorithm>
#include<math.h>
#include<string.h>
using namespace std;
const int maxn=2e5+;
int num[maxn];
int answer,block;
int vis[maxn];
struct node
{
int l,r,id;
int Ans;
}ans[maxn];
bool cmp(node x,node y)
{
if(x.l/block!=y.l/block)
return x.l<y.l;
if(x.l/block&) //使用波形排序，可进一步的优化
return x.r<y.r;
return x.r>y.r;
}
bool CMP(node x,node y)
{
return x.id<y.id;
}
void Delete(int pos)
{
vis[num[pos]]--;
if(!vis[num[pos]]&&num[pos]<answer){
answer=num[pos];
}
}
void add(int pos)
{
vis[num[pos]]++;
if(vis[num[pos]]==&&answer==num[pos]){
int tmp=answer+;
while(){
if(!vis[tmp]){
answer=tmp;
return;
}
tmp++;
}
}
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
block=sqrt(n);
for(int i=;i<=n;i++) scanf("%d",&num[i]);
for(int i=;i<=m;i++){
scanf("%d%d",&ans[i].l,&ans[i].r);
ans[i].id=i;
}
sort(ans+,ans++m,cmp);
int left=,right=;
for(int i=;i<=m;i++){
while(ans[i].l>left) Delete(left++);
while(ans[i].l<left) add(--left);
while(ans[i].r>right) add(++right);
while(ans[i].r<right) Delete(right--);
ans[i].Ans=answer;
}
sort(ans+,ans++m,CMP);
for(int i=;i<=m;i++)
printf("%d\n",ans[i].Ans);
return ;
}
还有一个权值线段树的解法：
对于第i棵权值线段树，维护一下数列前ii项中每个权值出现的最靠右的位置。然后向上更新一下最小值。这样如果某个权值最靠右的位置都比查询区间左端点小的话，那它一定没有在这个区间里出现。维护最小值目的就是看最小的是否比左端点大，根据这个在线段树上二分。
权值范围是10^9109的。题解里有说答案最大为nn，直接把>n>n的a[i]a[i]处理为n+1n+1就行。蒟蒻没有想到QAQQAQ，说一下蒟蒻的处理：
用离散化，但是一个权值没有在数列里出现过的话就不会在离散化数组中，也不会出现在线段树中，查询会出锅。注意到一个询问的答案要么是00，要么是数列中某个数的值+1+1。这样离散化时把00和每个出现过的权值+1+1都丢进去就行了QwQQwQ。
当然这道题不强制在线也不修改，可以把询问离线下来一边扫一边加，遇到询问右端点就查询左端点，不需要主席树（可持久化线段树），一棵权值线段树就可以了。
时间复杂度：O(nlogn)
#include<cstdio>
#include<algorithm>
#include<math.h>
#include<string.h>
#include<vector>
using namespace std;
const int maxn=2e5+;
int ans[maxn];
int t; //T为离散化之后的数组长度
int a[maxn],b[maxn*],cnt; //原数组和离散化的数组，以及下标cnt；
int tree[maxn<<];
int root[maxn];
void update(int root)
{
tree[root]=min(tree[root<<],tree[root<<|]);
}
void add(int num,int l,int r,int root,int base)
{
if(l==r){
tree[root]=base;
return;
}
int mid=l+r>>;
if(num<=mid) add(num,l,mid,root<<,base);
else add(num,mid+,r,root<<|,base);
update(root);
}
int query(int pos)
{
int l=,r=t;
int root=;
while(l<r){
int mid=l+r>>;
//如果左区间的值至少存在一个权值的下标小于pos的，就证明此范围内有符合条件的数；
//就像左边二分；
if(tree[root<<]<pos) r=mid,root=root<<;
//否则向右边二分；
else l=mid+,root=root<<|;
}
return b[l];
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
b[++cnt]=;
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
b[++cnt]=a[i];
b[++cnt]=a[i]+;
}
sort(b+,b++cnt);
t=unique(b+,b++cnt)-b-;
for(int i=;i<=n;i++){
a[i]=lower_bound(b+,b++t,a[i])-b;
add(a[i],,t,,i,root[i],root[i-]);
}
return ;
}
因为权值线段树能解这道题，所以用主席树解就显得没有必要了，但我还是练了练手。
#include<cstdio>
#include<algorithm>
#include<math.h>
#include<string.h>
using namespace std;
const int maxn=4e5+;
int a[maxn],b[maxn],cnt=,len;
struct node{int l,r,id;}tree[maxn<<];int cot;
//主席树需要开的空间比一般线段树更大，另外后面的cot是记录主席树节点用的。
int Root[maxn];
void build(int &x,int l,int r)
{
//这里的&x会把x得到的值传给这个变量，也就是Root[0];
//建一波空树，其实可以不建的，之前打过不建的代码，
//但总觉得不建的话心里不踏实。啊哈哈哈
x=++cot;
if(l==r) return ;
int mid=l+r>>;
build(tree[x].l,l,mid);
build(tree[x].r,mid+,r);
}
void add(int num,int l,int r,int &x,int y,int pos)
{
//同上，这里的&x会传给root[i];
tree[++cot]=tree[y];
x=cot; //将cot传给x,这个cot储存的是Root[i]这个节点的值，这个节点是根节点。
if(l==r){
tree[cot].id=pos;
//tree[x].id=pos; 这里也可以这样写
return;
}
int mid=l+r>>;
if(num<=mid) add(num,l,mid,tree[x].l,tree[y].l,pos);
else add(num,mid+,r,tree[x].r,tree[y].r,pos);
int left=tree[x].l,right=tree[x].r;
tree[x].id=min(tree[left].id,tree[right].id); //传递最小值；
}
int query(int pos,int base)
{
//这一部分是本题内容。
int l=,r=len;
while(l<r){
int mid=l+r>>;
//left存储的是根节点的左区间，right为右区间。
int left=tree[base].l,right=tree[base].r;
if(tree[left].id<pos) r=mid,base=left;
else l=mid+,base=right;
}
return b[l];
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
b[++cnt]=;
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
b[++cnt]=a[i];
b[++cnt]=a[i]+;
}
sort(b+,b++cnt);
len=unique(b+,b++cnt)-b-;
build(Root[],,len);
for(int i=;i<=n;i++){
a[i]=lower_bound(b+,b++len,a[i])-b;
add(a[i],,len,Root[i],Root[i-],i);
}
for(int i=;i<=m;i++){
int l,r;
scanf("%d%d",&l,&r);
int ans=query(l,Root[r]);
printf("%d\n",ans);
}
return ;
}