E.Complicated Computations

如果一個區間的$mex=a$，滿足以下條件：

• 區間未出現$a$
• 區間出現$1\to a?1$

因此若考慮是否存在一個區間的mex值是$a$，我們嘗試把整個區間以$a$為端點劃分成若干段，只要每一段內（不含端點a）中出現$1\to a?1$那么就存在一個區間的mex值是$a$
$$a\dots a\dots a\dots a\dots a\dots a\dots a$$
即只要有一個$\dots$存在$1\to a?1$那么就存在區間$mex=a$

那么如何確定$\dots$存在$1\to a?1$？
不妨假設兩個a的位置一個是$L$，一個是$R$，那么我們現在判定$[L+1,R?1]$的區間是否存在$1\to a?1$。那么不難發現$1\to a?1$最后一次出現的位置$>L$
由此用權值線段樹維護每一個數最后一次出現的位置，并且記錄上一次某數出現的位置查詢即可。

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<queue> #include<random> #include<bitset> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> #include<unordered_set> using namespace std; typedef long long ll; typedef pair<int,int> pii; const int mod=1e9+7; const int N=100010; int a[N],n; bool st[N]; int last[N]; int pos[N<<2]; void modify(int u,int l,int r,int k,int x) {if(l==r) {pos[u]=x;return;}int mid=l+r>>1;if(k<=mid) modify(u<<1,l,mid,k,x);else modify(u<<1|1,mid+1,r,k,x);pos[u]=min(pos[u<<1],pos[u<<1|1]); } int query(int u,int l,int r,int L,int R) {if(l>=L&&r<=R) return pos[u];int mid=l+r>>1;if(R<=mid)return query(u<<1,l,mid,L,R);else if(L>mid)return query(u<<1|1,mid+1,r,L,R);else return min(query(u<<1,l,mid,L,R),query(u<<1|1,mid+1,r,L,R)); } int main() {IO;int T=1;//cin>>T;for(int ca=1;ca<=T;ca++){cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++){if(a[i]!=1) st[1]=1;if(a[i]>1&&query(1,1,n,1,a[i]-1)>last[a[i]]) st[a[i]]=1;last[a[i]]=i;modify(1,1,n,a[i],i);}for(int i=2;i<=n+1;i++) //枚舉到n+1有可能有區間的mex=n+1if(query(1,1,n,1,i-1)>last[i]) st[i]=1;int res=1;while(st[res]) res++;cout<<res<<'\n';}return 0; }

這題竟然還卡時間？用build版本的線段樹就TLE，只能查詢時傳遞區間。。。

Hdu. Mex

大佬題解
$mex(1,i)$具有單調遞增的性質。

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0) #pragma GCC optimize(2) #include<set> #include<map> #include<cmath> #include<queue> #include<random> #include<bitset> #include<string> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<unordered_map> #include<unordered_set> using namespace std; typedef long long ll; typedef pair<int,int> pii; const int mod=1e9+7; const int N=200010; int a[N],n; int mex[N],ne[N],pos[N]; bool st[N]; struct node {int l,r;ll s;ll lazy; }tree[N<<2]; void pushup(int u) {tree[u].s=tree[u<<1].s+tree[u<<1|1].s; } void build(int u,int l,int r) {tree[u]={l,r,0,-1};if(l==r){tree[u].s=mex[l]; return;}int mid=l+r>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);pushup(u); } void pushdown(int u) {if(tree[u].lazy==-1) return;int lenl=tree[u<<1].r-tree[u<<1].l+1;int lenr=tree[u<<1|1].r-tree[u<<1|1].l+1;tree[u<<1].s=1ll*lenl*tree[u].lazy;tree[u<<1|1].s=1ll*lenr*tree[u].lazy;tree[u<<1].lazy=tree[u].lazy;tree[u<<1|1].lazy=tree[u].lazy;tree[u].lazy=-1; } void modify(int u,int l,int r,int x) {if(tree[u].l>=l&&tree[u].r<=r){tree[u].s=1ll*x*(tree[u].r-tree[u].l+1);tree[u].lazy=x;return;}pushdown(u);int mid=tree[u].l+tree[u].r>>1;if(l<=mid) modify(u<<1,l,r,x);if(r>mid) modify(u<<1|1,l,r,x);pushup(u); } ll query(int u,int l,int r) {if(tree[u].l>=l&&tree[u].r<=r) return tree[u].s;pushdown(u);int mid=tree[u].l+tree[u].r>>1;ll v=0;if(l<=mid) v+=query(u<<1,l,r);if(r>mid) v+=query(u<<1|1,l,r);return v; } int main() {while(scanf("%d",&n),n){for(int i=1;i<=n;i++){scanf("%d",&a[i]);if(a[i]>n) a[i]=n+1;}for(int i=0;i<=n+1;i++) st[i]=0;int now=0;for(int i=1;i<=n;i++){st[a[i]]=1;while(st[now]) now++;mex[i]=now;}for(int i=0;i<=n+1;i++) pos[i]=n+1;for(int i=n;i;i--){ne[i]=pos[a[i]];pos[a[i]]=i;}build(1,1,n);ll res=0;for(int i=1;i<=n;i++){res+=query(1,i,n);int l=i,r=ne[i]-1;while(l<r){int mid=l+r>>1;if(query(1,mid,mid)>a[i]) r=mid;else l=mid+1;}if(query(1,l,l)>a[i]) modify(1,l,ne[i]-1,a[i]);}printf("%lld\n",res);}return 0; }

總結

以上是生活随笔為你收集整理的mex性质学习的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。