Written with StackEdit.

題目描述

有一個(gè)長度為\(n\)的數(shù)組\({a_1,a_2,...,a_n}\)。\(m\)次詢問，每次詢問一個(gè)區(qū)間內(nèi)最小沒有出現(xiàn)過的自然數(shù)。

Input

第一行\(n,m\)。
第二行為\(n\)個(gè)數(shù)。
從第三行開始，每行一個(gè)詢問\(l,r\)。

Output

一行一個(gè)數(shù)，表示每個(gè)詢問的答案。

Sample Input

5 5
2 1 0 2 1
3 3
2 3
2 4
1 2
3 5

Sample Output

1
2
3
0
3

HINT

對于\(30\%\)的數(shù)據(jù)：
\(1<=n,m<=1000.\)

對于\(100\%\)的數(shù)據(jù):
\(1<=n,m<=200000，0<=ai<=10^9，1<=l<=r<=n.\)

Solution

• 多個(gè)區(qū)間詢問,可以離線,并且可以\(O(1)\)轉(zhuǎn)移,考慮使用莫隊(duì).
• 但是\(a_i\leq 10^9\),直接開個(gè)\(cnt\)數(shù)組記錄當(dāng)前區(qū)間內(nèi)的各種個(gè)數(shù)似乎不可做?
• 然而,對于大于\(n\)的元素,我們可以直接無視它.
• 一方面,它一定不會成為答案,否則需要出現(xiàn)至少\(0\)~\(n\) 這\(n+1\)個(gè)數(shù).
• 另一方面,它肯定不會對答案做出貢獻(xiàn).否則答案也會大于\(n\),據(jù)上,不可能.
• 所以\(a_i\)的范圍只是虛張聲勢...我們處理時(shí)將大于\(n\)的數(shù)都視作\(n+1\)即可.
• 然后就是一個(gè)愉快的莫隊(duì)板子題了.

#include<bits/stdc++.h> using namespace std; typedef long long LoveLive; inline int read() {int out=0,fh=1;char jp=getchar();while ((jp>'9'||jp<'0')&&jp!='-')jp=getchar();if (jp=='-'){fh=-1;jp=getchar();}while (jp>='0'&&jp<='9'){out=out*10+jp-'0';jp=getchar();}return out*fh; } const int MAXN=2e5+10; int cnt[MAXN]; set<int> s; int Ans[MAXN]; int n,m; int a[MAXN]; int belong[MAXN],BlockSize; int L,R,res; struct Query{int l,r;int id;bool operator < (const Query &rhs) const {if(belong[l]!=belong[rhs.l])return belong[l]<belong[rhs.l];return belong[r]<belong[rhs.r];} }q[MAXN]; void BuildBlocks() {BlockSize=sqrt(n);for(int i=1;i<=n;++i)belong[i]=(i/BlockSize)+1; } void add(int pos) {++cnt[a[pos]];for(int i=res;i<=n+2;++i)if(cnt[i]==0){res=i;return;} } void remove(int pos) {--cnt[a[pos]];if(cnt[a[pos]]==0)res=min(res,a[pos]); } int main() {n=read(),m=read();for(int i=1;i<=n;++i)a[i]=read(),a[i]=a[i]>n?n+1:a[i];for(int i=1;i<=m;++i){q[i].id=i;q[i].l=read();q[i].r=read(); }for(int i=0;i<=n;++i)s.insert(i);a[0]=n+2;BuildBlocks();sort(q+1,q+1+m);L=0,R=0;for(int i=1;i<=m;++i){int l=q[i].l,r=q[i].r;while(L<l)remove(L),++L;while(L>l)--L,add(L);while(R<r)++R,add(R);while(R>r)remove(R),--R;Ans[q[i].id]=res;}for(int i=1;i<=m;++i)printf("%d\n",Ans[i]);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/jklover/p/10105545.html

總結(jié)

以上是生活随笔為你收集整理的bzoj 3585 mex的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。