BZOJ 3585.mex

首先这题不需要离散化,而是动态开点。

如果是序列整体 mex\text{mex} 考虑权值线段树。
每个结点维护其值域区间中有没有数没出现过。

然后就从根结点开始,优先考虑左子树,
直到叶子结点或该子树为空,此时答案就是该结点值域区间的左端点。

现在考虑区间 mex\text{mex}
我们让每个叶子结点维护该权值最后一次出现的位置,非叶子结点维护这个值域区间最早的最后出现的位置。

考虑离线。
把询问按照 rr 排序,然后从 11nn 依次插入每个数,每次插入完第 ii 个数就考虑 r=ir = i 的询问。
于是在权值线段树上找最小的最后出现的位置 <l< l 的,因为 rr 以后的数没有被插入,无需考虑其对答案的影响。
具体过程类似,从根结点优先考虑左子树,如果左子树最早的最后出现位置 <l< l,就说明左子树有至少一个满足要求的权值。
于是一直找直到子树为空或遇到叶子。

考虑在线。
可持久化出 nn 棵主席树,询问就直接在第 rr 棵上面查找。

此代码无法在 BZOJ 上通过。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <cstdio>
#include <algorithm>
#define ls(p) seg[p].lson
#define rs(p) seg[p].rson
using namespace std;
const int N = 2e5;
const int A = 1e9;
int n,m;
int a[N + 10],rt[N + 10];
struct node
{
int last;
int lson,rson;
} seg[(N << 7) + 10];
inline int copy_node(int p)
{
static int tot = 0;
seg[++tot] = seg[p];
return tot;
}
void change(int x,int k,int &p,int tl,int tr)
{
p = copy_node(p);
if(tl == tr)
{
seg[p].last = k;
return ;
}
int mid = tl + tr >> 1;
if(x <= mid)
change(x,k,ls(p),tl,mid);
else
change(x,k,rs(p),mid + 1,tr);
seg[p].last = min(seg[ls(p)].last,seg[rs(p)].last);
}
int query(int x,int p,int tl,int tr)
{
if(!p || tl == tr)
return tl;
int mid = tl + tr >> 1;
if(seg[ls(p)].last < x)
return query(x,ls(p),tl,mid);
else
return query(x,rs(p),mid + 1,tr);
}
int main()
{
scanf("%d%d",&n,&m);
for(register int i = 1;i <= n;++i)
scanf("%d",a + i),change(a[i],i,rt[i] = rt[i - 1],0,A);
int l,r;
while(m--)
{
scanf("%d%d",&l,&r);
printf("%d\n",query(l,rt[r],0,A));
}
}