P4137
solution 1：
我最初做这题是莫队，这是一道练习莫队+值域分块的好题。
莫队的时候记录两个东西，\(b_i\) 表示 \(i\) 在当前出现的次数，\(c_i\) 表示值域第 \(i\) 块中有出现的数的个数。
显然 \(b,c\) 都是可以满足莫队 \(O(1)\) 移动指针。
而后查询枚举值域块，令 \(len_i\) 表示值域第 \(i\) 块大小。如果找到第一个 \(c_i\neq len_i\)，则 mex 一定在第 \(i\) 块中，
这时枚举块中元素判断出现次数是否 \(>0\) 即可。回答询问是 \(O(\sqrt V)\) 的。
\(n,V\) 同阶，总复杂度是 \(O(n\sqrt n)\) 的。
$\texttt{code}$
#include<bits/stdc++.h>
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=2e5+6,len=450;
#define bl(x) (x-1)/len+1
struct node
{
int l,r,id;
bool operator<(node x){return (bl(l)^bl(x.l))?(l<x.l):((bl(l)&1)?r<x.r:r>x.r);}
}a[N];
int n,m,b[N],cnt[len],cnt1[N],L[len],R[len],ans[N];
inline void add(int x){(!cnt1[b[x]])&&(cnt[bl(b[x])]++);cnt1[b[x]]++;}
inline void del(int x){(cnt1[b[x]]==1)&&(cnt[bl(b[x])]--);cnt1[b[x]]--;}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=bl(N-5);i++) L[i]=(i-1)*len+1,R[i]=i*len;R[bl(N-5)]=N-5;
for(int i=1;i<=n;i++) scanf("%d",&b[i]),b[i]++;
int l,r;
for(int i=1;i<=m;i++) scanf("%d%d",&l,&r),a[i]={l,r,i};
sort(a+1,a+1+m);l=1;r=0;
for(int i=1;i<=m;i++)
{
while(l>a[i].l) add(--l);
while(r<a[i].r) add(++r);
while(l<a[i].l) del(l++);
while(r>a[i].r) del(r--);
int wz=0;
for(int j=1;j<=bl(N-5);j++) if(cnt[j]!=R[j]-L[j]+1){wz=j;break;}
for(int j=L[wz];j<=R[wz];j++) if(!cnt1[j]){ans[a[i].id]=j;break;}
}
for(int i=1;i<=m;i++) printf("%d\n",ans[i]-1);
return 0;
}
solution 2：
这时洛谷第一篇题解的做法。
从左往右扫一遍，在权值线段树（要可持久化一下）上修改当前权值对应的最后一次出现的位置为当前位置。
查询区间 \([l,r]\) 时，答案就是第 \(r\) 棵线段树上，第一个最后一次出现的位置小于 \(l\) 的权值。
其实也可以不可持久化的，只需把询问离线一下。（但是我下面讲的就算半在线了）
复杂度 \(O(n\log n)\)。
$\texttt{code}$
#include<bits/stdc++.h>
#define LL long long
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=2e5+5;
int n,m,V,a[N],tot,rt[N];
struct node{int ls,rs,x;}b[N*25];
void build(int l,int r,int &wz)
{
b[wz=++tot]={0,0,0};if(l==r) return;
int mid=(l+r)>>1;build(l,mid,b[wz].ls);build(mid+1,r,b[wz].rs);
}
void updata(int l,int r,int &wz,int wz1,int x,int y)
{
b[wz=++tot]=b[wz1];if(l==r) return b[wz].x=y,void();
int mid=(l+r)>>1;
if(x<=mid) updata(l,mid,b[wz].ls,b[wz1].ls,x,y);
else updata(mid+1,r,b[wz].rs,b[wz1].rs,x,y);
b[wz].x=min(b[b[wz].ls].x,b[b[wz].rs].x);
}
int query(int l,int r,int wz,int x)
{
if(l==r) return l;int mid=(l+r)>>1;
if(b[b[wz].ls].x<x) return query(l,mid,b[wz].ls,x);
return query(mid+1,r,b[wz].rs,x);
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i],V=max(V,a[i]);V+=3;build(1,V,rt[0]);
for(int i=1;i<=n;i++) updata(1,V,rt[i],rt[i-1],a[i]+1,i);
while(m--)
{
int l,r;cin>>l>>r;
cout<<query(1,V,rt[r],l)-1<<"\n";
}
return 0;
}
CF1436E
我们考虑是否存在一个子区间，满足其 mex 为 \(x\)。
首先，这个子区间里面必须要没有 \(x\)，
于是我们首先把数组中所有的 \(x\) 找出来，这些 \(x\) 把数组分成了若干段，我们要的子数组必须不能跨越这些段。
由于 \(t\) 个数会把数组分成了 \(O(t)\) 段。于是对于所有数，我们总共会分 \(O(n)\) 段。
于是我们对每个段，按上一题的方法查询 mex，判断是否 \(\text{mex}=x\)，就可以知道是否存在 mex 为 \(x\) 的子区间。
若 \(x\) 是第一个不存在这样子区间的，那么答案就是 \(x\)。
设 \(\max(a)=V\)，则答案的范围为 \([1,V+2]\)，需要多查两个数，对于没出现过的数查询 \([1,n]\) 的 mex 是否为它即可。具体细节看代码。
复杂度取决于你上一题的写法，如果莫队就是 \(O(n\sqrt n)\)，可持久化线段树就是 \(O(n\log n)\)。
$\texttt{code}$
#include<bits/stdc++.h>
#define LL long long
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=1e5+5;
int n,V,a[N],tot,rt[N];
vector<int>g[N];
struct node{int ls,rs,x;}b[N*25];
void build(int l,int r,int &wz)
{
b[wz=++tot]={0,0,0};if(l==r) return;
int mid=(l+r)>>1;build(l,mid,b[wz].ls);build(mid+1,r,b[wz].rs);
}
void updata(int l,int r,int &wz,int wz1,int x,int y)
{
b[wz=++tot]=b[wz1];if(l==r) return b[wz].x=y,void();
int mid=(l+r)>>1;
if(x<=mid) updata(l,mid,b[wz].ls,b[wz1].ls,x,y);
else updata(mid+1,r,b[wz].rs,b[wz1].rs,x,y);
b[wz].x=min(b[b[wz].ls].x,b[b[wz].rs].x);
}
int query(int l,int r,int wz,int x)
{
if(l==r) return l;int mid=(l+r)>>1;
if(b[b[wz].ls].x<x) return query(l,mid,b[wz].ls,x);
return query(mid+1,r,b[wz].rs,x);
}
inline int que(int l,int r){return query(1,V,rt[r],l);}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;
V=n+3;for(int i=1;i<=V;i++) g[i].push_back(0);
for(int i=1;i<=n;i++) cin>>a[i],g[a[i]].push_back(i);
build(1,V,rt[0]);for(int i=1;i<=n;i++) updata(1,V,rt[i],rt[i-1],a[i],i);
for(int i=1;i<=V;i++)
{
g[i].push_back(n+1);bool ok=0;
for(int j=0;j<g[i].size()-1;j++)
{
int l=g[i][j]+1,r=g[i][j+1]-1;
if(l<=r&&que(l,r)==i){ok=1;break;}
}
if(!ok) return cout<<i,0;
}
return 0;
}
CF1740H
你先别急。
标签：总结,int,void,mid,wz,build,数据结构,mex From： https://www.cnblogs.com/HaHeHyt/p/17682238.html