正題

評(píng)測(cè)記錄:https://www.luogu.org/recordnew/lists?uid=52918&pid=P4137

---

題目大意

求區(qū)間mex。

---

解題思路

開始發(fā)現(xiàn)$a_i$很大，開不了桶。但是轉(zhuǎn)念一想，如果$ans>n+1$僅當(dāng)前n+1個(gè)都有，可是最多只有n個(gè)，所以$>n$的都沒用。
之后開個(gè)桶+莫隊(duì)分塊優(yōu)化就行了。

---

code

#include<cstdio> #include<cmath> #include<algorithm> #define N 200010 using namespace std; struct node{int l,r,id,pos; }a[N]; int n,m,w[N],l,r,now,id[N],t; int cnt[N],ans[N]; bool cmp(node x,node y){return x.pos<y.pos||(x.pos==y.pos&&x.r<y.r); } void add(int x) {if(w[x]>n) return;cnt[w[x]]++;while(cnt[now]) now++; } void del(int x) {if(w[x]>n) return;cnt[w[x]]--;if(!cnt[w[x]]) now=min(now,w[x]); } int main() {scanf("%d%d",&n,&m);t=sqrt(n);for(int i=1;i<=n;i++)scanf("%d",&w[i]);for(int i=1;i<=m;i++)scanf("%d%d",&a[i].l,&a[i].r),a[i].id=i,a[i].pos=(a[i].l-1)/t+1;sort(a+1,a+1+m,cmp);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--);ans[a[i].id]=now;//for(int j=0;j<=5;j++)// printf("%d ",cnt[j]);//printf(":%d-%d\n",a[i].l,a[i].r);}for(int i=1;i<=m;i++)printf("%d\n",ans[i]); }

總結(jié)

以上是生活随笔為你收集整理的P4137-Rmq Problem/mex【莫队,分块】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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