【洛谷P4137】Rmq Problem / mex【主席树】

本文主要是介绍【洛谷P4137】Rmq Problem / mex【主席树】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意：

题目链接：https://www.luogu.org/problemnew/show/P4137
有一个长度为$n$的数组 { a 1 , a 2 , … , a n } \{a1,a2,…,an\} {a1,a2,…,an}。$m$次询问，每次询问一个区间内最小没有出现过的自然数。

---

思路：

显然主席树。
对于第$k$棵线段树，设叶子节点$i$表示在数列前$k$个数字中，数字$i$出现的最后位置。
显然$a[]$的范围是吓人的。最终答案一定不会$>n+1$，所以读入到$x(x>n)$之后直接把$x$变成$n+1$就可以了。
对于任意一个询问$x,y$，意思就是说在第y棵线段树中找到第一个叶子结点最后出现的位置<l。
可以在任意区间$[l,r]$中记录$min$表示$[l,r]$中最后出现位置最前的位置。
那么对于任意区间，如果左儿子$min$小于$l$，答案就在左边，否则在右边。
时间复杂度$O(nlogn)$

---

代码：

#include <cstdio>
#include <algorithm>
using namespace std;const int N=200010;
int n,T,tot,x,y,root[N];struct Tree
{int ls,rs,last,min;
}tree[N+N*20];int build(int l,int r)
{int p=++tot;if (l==r) return p;int mid=(l+r)/2;tree[p].ls=build(l,mid);tree[p].rs=build(mid+1,r);return p;
}int insert(int now,int l,int r,int x,int val)
{int p=++tot;tree[p]=tree[now];if (l==r){tree[p].last=tree[p].min=val;return p;}int mid=(l+r)/2;if (x<=mid) tree[p].ls=insert(tree[now].ls,l,mid,x,val);else tree[p].rs=insert(tree[now].rs,mid+1,r,x,val);tree[p].min=min(tree[tree[p].ls].min,tree[tree[p].rs].min);return p;
}int ask(int x,int l,int r,int val)
{if (l==r) return r;  //找到答案int mid=(l+r)/2;if (tree[tree[x].ls].min>=val) return ask(tree[x].rs,mid+1,r,val);else return ask(tree[x].ls,l,mid,val); 
}int main()
{scanf("%d%d",&n,&T);root[0]=build(0,n);for (int i=1;i<=n;i++){scanf("%d",&x);if (x<=n) root[i]=insert(root[i-1],0,n,x,i);  //插入else root[i]=insert(root[i-1],0,n,n+1,i);}while (T--){scanf("%d%d",&x,&y);printf("%d\n",ask(root[y],0,n,x)); }return 0;
}

这篇关于【洛谷P4137】Rmq Problem / mex【主席树】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---