Mex

問題提出

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

題目解答

對$1?n$這里能夠的每個數(shù)$x$,都統(tǒng)計出來在數(shù)組中出現(xiàn)的位置,并在前補上$0$,在后補上$n+1$.

例如數(shù)組$\{1,2,3,2,1\}$,
其中$1$出現(xiàn)過的位置就是:$\{0,1,5,6\}$
其中$2$出現(xiàn)過的位置就是:$\{0,2,4,6\}$
其中$3$出現(xiàn)過的位置就是:$\{0,3,6\}$
其中$4$出現(xiàn)過的位置就是:$\{0,6\}$
其中$5$出現(xiàn)過的位置就是:$\{0,6\}$

如果一個自然數(shù)$x$沒有在一個區(qū)間$[l,r]$中出現(xiàn)過,那么必然存在$x$的出現(xiàn)序列中的兩個位置$p_1,p_2$滿足$p_1<l<r<p_2$.

那么這就變成一個經(jīng)典的$2$維數(shù)點問題啦!

我們把每個$x$的出現(xiàn)位置序列,相鄰兩個數(shù)并成一個二維數(shù)點,插入到線段樹中去.

對于每個詢問$(l,r)$在線段樹中找滿足$p_1<l<r<p_2$條件的權(quán)值最小的點就可以了.

將所有的詢問$(l,r)$和數(shù)點$p_1,p_2$按照第二維排序,從左往右枚舉,遇到詢問就回答,遇到數(shù)點就插入.

排序可以省掉一維.

代碼

#include <iostream> #include <algorithm> #include <cstring> #include <vector> #include <map> #define pr(x) std::cout << #x << ':' << x << std::endl #define rep(i,a,b) for(int i = a;i <= b;++i) #define repi(i,a,b) for(int i = a;i >= b;--i) #define clr(x) memset(x,0,sizeof(x)) #define setinf(x) memset(x,0x3f,sizeof(x))const int N = 200010; const int inf = 1e9+7; int n,m; int a[N]; std::map<int,int> map;struct node{int num;node(int x = inf){num = x;} }ns[N<<2];struct que{int l,r,id;que(int l = 0,int r = 0,int id = 0) {this->l = l,this->r = r,this->id = id;}bool operator<(const que &q)const{return l < q.l;} }qs[N],qs2[N<<2];int ans[N];node maintain(node &lch,node &rch) {node res = node();res.num = std::min(lch.num,rch.num);return res; } void change(int o,int l,int r,int pos,int val) {if(l == r) {if(val < ns[o].num) ns[o].num = val;return ;}int mid = (l + r) >> 1;if(pos <= mid) change(o<<1,l,mid,pos,val);else change(o<<1|1,mid+1,r,pos,val);ns[o] = maintain(ns[o<<1],ns[o<<1|1]); }node query(int o,int l,int r,int ql,int qr) {if(ql <= l && r <= qr) return ns[o];if(r < ql || qr < l)return node(); int mid = (l + r) >> 1;node lch = query(o<<1,l,mid,ql,qr);node rch = query(o<<1|1,mid+1,r,ql,qr);return maintain(lch,rch); }void build(int o,int l,int r) {if(l == r) {ns[o] = node();return ;}int mid = (l + r) >> 1;build(o<<1,l,mid);build(o<<1|1,mid+1,r);ns[o] = maintain(ns[o<<1],ns[o<<1|1]); }int main() {std::ios::sync_with_stdio(false);std::cin >> n >> m;build(1,0,n+1);rep(i,1,n) std::cin >> a[i];int cc = 0;rep(i,1,n){qs2[cc++] = que(map[a[i]],i,a[i]);map[a[i]] = i;}rep(i,0,2*n) {qs2[cc++] = que(map[i],n+1,i);}std::sort(qs2,qs2+cc);rep(i,1,m) {std::cin >> qs[i].l >> qs[i].r;qs[i].id = i;} std::sort(qs+1,qs+1+m);int pos = 0;rep(i,1,m) {while(pos < cc && qs2[pos].l < qs[i].l){change(1,0,n+1,qs2[pos].r,qs2[pos].id);++pos;}node res = query(1,0,n+1,qs[i].r+1,n+1);ans[qs[i].id] = res.num;}rep(i,1,m) {std::cout << ans[i] << std::endl;}}

總結(jié)

以上是生活随笔為你收集整理的线段树-Mex-洛谷P4137的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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