首页 > 代码库 > bzoj 3585: mex
bzoj 3585: mex
3585: mex
Time Limit: 20 Sec Memory Limit: 128 MBSubmit: 969 Solved: 511
[Submit][Status][Discuss]
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
2 1 0 2 1
3 3
2 3
2 4
1 2
3 5
Sample Output
1
2
3
0
3
2
3
0
3
HINT
数据规模和约定
对于100%的数据:
1<=n,m<=200000
0<=ai<=109
1<=l<=r<=n
对于30%的数据:
1<=n,m<=1000
以权值为下标,
minn[i]=j,表示i所代表的权值为[l,r]的区间,最早出现的位置为j
例:0 2 1 0 1 3 2
对于root[7]来说,
[0,3]=1, 0最早出现在第1个位置
[1,3]=2, 2最早出现在第2个位置
查询[l,r]时,在root[r]里查询
如果左子区间的minn>=l,说明权值小的左边一半都最早出现在l以后,就往右孩子找
否则,说明权值小的左边一半有没有出现在l之后的,就往左孩子找
因为是在root[r]里,所以保证不超过右边界
对于10^9的权值,离散化?
不。
如果权值>n,直接让它=n
因为此时<n中一定有没有出现的数
#include<cstdio>#include<cstring>#include<algorithm>#define N 200001using namespace std;int n,q,tot;int root[N],minn[N*20]; int lc[N*20],rc[N*20]; void change(int &now,int pre,int l,int r,int pos,int val) { if(!now) now=++tot; if(l==r) { minn[now]=val; return; } int mid=l+r>>1; if(pos<=mid) { change(lc[now],lc[pre],l,mid,pos,val); rc[now]=rc[pre]; } else { change(rc[now],rc[pre],mid+1,r,pos,val); lc[now]=lc[pre]; } minn[now]=min(minn[lc[now]],minn[rc[now]]); } int query(int now,int l,int r,int pos) { if(l==r) return l; int mid=l+r>>1; if(minn[lc[now]]>=pos) return query(rc[now],mid+1,r,pos); return query(lc[now],l,mid,pos); }int main(){ freopen("mex.in","r",stdin); freopen("mex.out","w",stdout); int m; scanf("%d%d",&n,&m); int x; for(int i=1;i<=n;i++) { scanf("%d",&x); if(x>n) x=n; change(root[i],root[i-1],0,n,x,i); } int l,r; while(m--) { scanf("%d%d",&l,&r); printf("%d\n",query(root[r],0,n,l)); }}
bzoj 3585: mex
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。