bzoj3585 mex

bzoj3585 mex

​​ Description

有一个长度为n的数组{a1,a2,…,an}。m次询问，每次询问一个区间内最小没有出现过的自然数。

Input

第一行n,m。 第二行为n个数。 从第三行开始，每行一个询问l,r。

Output

一行一个数，表示每个询问的答案。

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

数据规模和约定

对于100%的数据：

1<=n,m<=200000

0<=ai<=109

1<=l<=r<=n

对于30%的数据：

1<=n,m<=1000

这题相比上一篇博文 相当于加入了一个离散化 而且因为我们需要求集合中最小没有出现的，那么在离散化过程中是不允许出现相同的

那么针对这种离散化 我们使用unique这个函数去重，但是这个函数去重的原理是把相邻的相同的移动到后面，所以我们必须保证这个序列是有序的

首先对它备份一下，然后排序，去重，unique返回的是去完重最后一个指针的位置

我们可以算出去重后的长度

然后照样和之前mex一样 统计1~i的mex

id[i]是我们离散化之后的值，相当于认为i这个地方存的是id[i]而非a1[i]

if (a1[i]==tmp)while (f[x]) {++tmp;if (a[++x]!=tmp) break;} 如果我现在的数等于我1~i的mex了 那么我就需要寻找下一个没出现的点

如果离散化后这个点出现过我就一直++直到在有序的a中没有出现

#include#include#define inf 0x7f7f7f7f#define N 220000using namespace std;inline int read(){ int x=0;char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar(); } return x;}int id[N],ans[N],last[N],next[N],mex[N],root,num,n,m,a[N],a1[N];bool f[N];struct node{ int l,r,id;}q[N];struct node1{ int l,r,left,right,min;}tree[N<<2];inline bool cmp(node a,node b){ return a.l>1; build(tree[x].left,l,mid);build(tree[x].right,mid+1,r);}inline void pushdown(int x){ int l=tree[x].left,r=tree[x].right; tree[l].min=min(tree[l].min,tree[x].min); tree[r].min=min(tree[r].min,tree[x].min);}int query(int x,int l){ if(tree[x].l==tree[x].r)return tree[x].min; int mid=tree[x].l+tree[x].r>>1;pushdown(x); if (l<=mid) return query(tree[x].left,l);else return query(tree[x].right,l);}void change(int x,int l,int r,int v){ if (l<=tree[x].l&&r>=tree[x].r){tree[x].min=min(tree[x].min,v);return;} int mid=tree[x].l+tree[x].r>>1;pushdown(x); if (l<=mid) change(tree[x].left,l,r,v); if (r>mid) change(tree[x].right,l,r,v);}int main(){ freopen("bzoj3585.in","r",stdin); n=read();m=read(); for (int i=1;i<=n;++i) {a[i]=read(),a1[i]=a[i];} sort(a+1,a+n+1); int nn=unique(a+1,a+n+1)-a-1;int tmp=0; for (int i=1;i<=n;++i){ int x=lower_bound(a+1,a+nn+1,a1[i])-a;id[i]=x;f[id[i]]=1;last[id[i]]=n+1; //printf("%d,x); if (a1[i]==tmp)while (f[x]) {++tmp;if (a[++x]!=tmp) break;} mex[i]=tmp; } for (int i=1;i<=m;++i){q[i].id=i;q[i].l=read();q[i].r=read();} //for (int i=1;i<=n;++i) printf("%d,mex[i]); for (int i=n;i>=1;--i){next[i]=last[id[i]];last[id[i]]=i;} sort(q+1,q+m+1,cmp);build(root,1,n);int l=1; for (int i=1;i<=m;++i){ while(l

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。