bzoj3339 rmq problem

bzoj3339 rmq problem

​​ Description

Input

Output

Sample Input

7 5 0 2 1 0 1 3 2 1 3 2 3 1 4 3 6 2 7 Sample Output

3 0 3 2 4 HINT

Source

By Xhr

MEX看题目大概就知道这是什么高端的东西了

第二次敲，觉得比上次清楚很多 本来不想写思路了，但刚刚和滕老师通话，滕老师让我多想，写完之后再写再想做熟，所以我决定再理清一下思路，一会儿还打算写bzoj上的另一个mex的题

这题需要我们去查询这个区间内 最小没有出现的

首先我们可以0(1)去处理出1~i这个区间的mex值

然后我们需要记录一下a[i]这个值下一次出现的位置

然后我们把询问离线，按照左端点排序

既然我们o(1)处理出1~i接下来就是我们要如何从1转移到后面了

关于左端点向右移动，那么我们相当于就是少了a[i]这个地方的限制，所以我们要在这之间去更新一下我们a[l]这个值

#include#include#define N 220000#define inf 0x7f7f7f7fusing 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;}struct node{ int l,r,id;}q[N];struct node1{ int l,r,left,right,min;}tree[N<<2];int mex[N],a[N],n,q1,ans[N],num,last[N],next[N],root;bool f[N];inline bool cmp(node a,node b){return a.l>1;pushdown(x); if (l<=mid) return query(tree[x].left,l);else return query(tree[x].right,l);}void build(int &x,int l,int r){ x=++num;tree[x].l=l;tree[x].r=r;tree[x].min=inf; if (l==r){tree[x].min=mex[l];return;} int mid=l+r>>1; build(tree[x].left,l,mid);build(tree[x].right,mid+1,r);}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("bzoj3339.in","r",stdin); n=read();q1=read();int tmp=0; for (int i=1;i<=n;++i) { a[i]=read();f[a[i]]=true;last[a[i]]=n+1; if (a[i]==tmp) while (f[tmp]) tmp++; mex[i]=tmp; } for (int i=n;i>=1;--i) {next[i]=last[a[i]];last[a[i]]=i;} for (int i=1;i<=q1;++i){int l=read(),r=read();q[i].id=i;q[i].l=l;q[i].r=r;} sort(q+1,q+q1+1,cmp);int l=1;build(root,1,n); for (int i=1;i<=q1;++i){ while (l

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