AHSOFNU NOIP模拟题-3 T4/BZOJ 3339(离线+线段树)

此题在线做很麻烦,而且这题也不强制在线,不会修改$A$的值,那就离线吧。
先求出$[1, i]$的$mex$值,然后求出$nxt$值,即下一个为该数值的下标,没有就是$0$,可以很容易$O(n)$推出来
然后考虑从$A[1]$开始删数,即考虑$A[i]$对后面的$mex$值的影响
可以发现,删去$A[i]$后,$i$到$nxt[i]-1$都会受影响,并且这个范围内$mex$大于$A[i]$的都要等于$A[i]$,这里的修改可以线段树完成,有点麻烦。那么对查询区间按左端点排序,然后依次删数,发现一个区间的$mex$值就是线段树上单点查询右端点的值。(实际上线段树上单点查询$i$表示为删了几个数$+1$到$i$之间的$mex$值)

注意此题卡输入,一定要输入优化,以后做题要测一测极限数据,看看大概时间,如果输入数据很大的话,也要考虑输入优化。

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define FN2 "mex"
using namespace std;
const int MAXN = 200000 + 5, INF = 1000000000;
struct inv {
int no, l, r;
bool operator < (const inv &b) const {
return l < b.l;
}
}qj[MAXN];
int n, q, A[MAXN], mex[MAXN], mk[MAXN], nxt[MAXN], ans[MAXN];
#define M ((l+r)>>1)
#define lc (o<<1)
#define rc (o<<1|1)
int lazy[MAXN*4];
int read()
{
int x=0;char ch=getchar();
while(ch<'0'||ch>'9'){ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x;
}
void pushdown(int o, int l, int r) {
if (lazy[o]!=INF) {
if (l!=r) lazy[lc] = min(lazy[lc], lazy[o]);
if (l!=r) lazy[rc] = min(lazy[rc], lazy[o]);
}
}
void build(int o, int l, int r) {
if (l==r) lazy[o] = mex[l]; else lazy[o] = INF, build(lc, l, M), build(rc, M+1, r);
}
void update(int o, int l, int r, int x, int y, int w) {
pushdown(o, l, r);
if (x<=l&&r<=y) {
lazy[o] = min(lazy[o], w);
return ;
}
if (x<=M) update(lc, l, M, x, y, w);
if (M<y) update(rc, M+1, r, x, y, w);
}
int query(int o, int l, int r, int p) {
pushdown(o, l, r);
if (l==r) {
return lazy[o];
}
if (p<=M) return query(lc, l, M, p);
else if (M<p) return query(rc, M+1, r, p);
}
void clean() {
ms(mk, false), ms(nxt, 0);
}
void solve() {
clean();
int k = 0;
for (int i=1;i<=n;i++) {
A[i] = read();
mk[A[i]] = true;
if (mk[k]) {
while (mk[k]) k++;
}
mex[i] = k;
}
ms(mk, false);
for (int i=n;i>0;i--) {
nxt[i] = mk[A[i]];
mk[A[i]] = i;
}
build(1,1,n);
for (int i=1;i<=q;i++) qj[i].l = read(), qj[i].r = read(), qj[i].no = i;
sort(qj+1, qj+1+q), k = 1;
for (int i=1;i<=q;i++) {
while (k!=qj[i].l) {
if (nxt[k]==0) update(1,1,n,k,n,A[k]); else update(1,1,n,k,nxt[k]-1,A[k]);
k++;
}
ans[qj[i].no] = query(1,1,n,qj[i].r);
}
for (int i=1;i<=q;i++) printf("%d\n", ans[i]);
}
int main() {
freopen(FN2".in", "r", stdin); freopen(FN2".out", "w", stdout);
scanf("%d%d", &n, &q), solve();
fclose(stdin); fclose(stdout);
return 0;
}

------ 本文结束 ------