BJOI2019 删数(贪心,线段树)

题目链接

洛谷

LOJ

BZOJ

题意简述

一个数列是“可删除的”,当且仅当可以通过这种操作将其清空:将数列中等于这个数列长度的数删去。

如,$[1, 2, 4, 4]$ 是“可删除的”,第一次操作删成 $[1, 2]$,第二次操作删成 $[1]$,第三次操作清空。

定义一个数列的权值为至少需要进行的单点修改数目,使得这个数列变成“可删除的”。

现在给你一个数列 $a_{1..n}$,以及 $m$ 次修改操作,你需要在每次修改后回答这个数列的权值。

修改操作有三种:

  1. 单点修改。
  2. 全局加一。
  3. 全局减一。

$1\le n,m\le 150000$,数列初始值以及单点修改成的值在 $[1,n]$ 内,但全局修改可能使数列中的元素超过这个范围。

简要做法

计算数列的权值

如果将数 $i$ 出现的次数 $cnt[i]$ 看做一个高度为 $cnt[i]$、放在位置 $i$ 的柱子,让所有柱子向左倒,每个位置就会被若干个柱子覆盖。也就是说,$i$ 这个柱子覆盖了 $[i-cnt[i]+1,i]$。

一个数列是“可删除的”当且仅当 $[1,n]$ 都被恰好覆盖了一次。

并且,一个数列的权值就是它没被覆盖的位置数量,证明如下:

  1. 这是答案的下界,因为每次单点修改最多覆盖一个新位置。
  2. 这是答案的上界,因为你可以把重复覆盖的换到未覆盖处。

全局修改

全局修改会导致 $cnt$ 以及覆盖数量发生位移,所以可以考虑使用一个标记 $delta$ 来表示现在全局加了多少,那么 $cnt[i]$ 表示 $cnt[i+delta]$,位置 $i$ 被覆盖的次数被记录在 $i-delta$ 处,$a[i]$ 表示 $a_i-delta$。

需要特别注意的是,全局加时需要减去原来位置 $n$ 的贡献,因为它们来到 $n+1$ 后必定会是累赘,全局减时要再加回来。但不需要特殊处理位置 $1$ 的贡献,因为覆盖是向左的,查询时只会查询 $[1,n]$ 的覆盖次数,小于 $1$ 的位置对答案没有影响。

可以用线段树维护覆盖次数。

实现细节

使用一个线段树来维护覆盖次数,它支持区间加减、区间查询最小值及其出现次数。

下面是实现的细节。(代码中所有 $cnt$ 的下标都要加上 $m$ 避免负数下标。)

单点修改

首先处理原来的 $a_p$。

先判断 $a_p$ 是否小于等于 $n$,只有 $a_p\le n$ 时才会有贡献,也就是说,当 $a[p]+delta\le n$ 时需要在线段树上 $a[p]-cnt[a[p]]+1$ 处单点减一。

然后将 $cnt[a[p]]$ 减一。

接着处理新增的 $x$。

$x$ 必定在 $[1,n]$ 内,所以一定需要在线段树上 $x-cnt[x-delta]-delta$ 处单点加一。

然后将 $cnt[x-delta]$ 加一。

最后将 $a[p]$ 修改为 $x-delta$。

全局加

需要减去位置 $n$ 的贡献:$[n-cnt[n-delta]+1-delta,n-delta]$ 区间减一。

然后将 $delta$ 加一。

全局减

先将 $delta$ 减一。

然后加上位置 $n$ 的贡献:$[n-cnt[n-delta]+1-delta,n-delta]$ 区间加一。

查询答案

查询 $[1-delta,n-delta]$ 的最小值及出现次数。

若最小值不为 $0$ 则答案为 $0$。

否则答案为最小值的出现次数。

参考代码

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include <iostream>
#include <cstdio>

using namespace std;

const int N = 150010;

struct Min
{
int val, cnt;
Min(int _val = 0, int _cnt = 0): val(_val), cnt(_cnt) {}
};

Min merge(Min a, Min b)
{
if (a.val < b.val) return a;
if (b.val < a.val) return b;
return Min(a.val, a.cnt + b.cnt);
}

struct SegmentTree
{
#define ls (cur << 1)
#define rs (cur << 1 | 1)
#define mid ((l + r) >> 1)

Min mn[N << 4];
int tag[N << 4];

void pushup(int cur)
{
mn[cur] = merge(mn[ls], mn[rs]);
}

void add(int cur, int x)
{
mn[cur].val += x;
tag[cur] += x;
}

void pushdown(int cur)
{
add(ls, tag[cur]);
add(rs, tag[cur]);
tag[cur] = 0;
}

void build(int cur, int l, int r)
{
if (l == r - 1) mn[cur] = Min(0, 1);
else
{
build(ls, l, mid);
build(rs, mid, r);
pushup(cur);
}
}

void add(int cur, int l, int r, int L, int R, int x)
{
if (l >= R || r <= L) return;
if (L <= l && r <= R) add(cur, x);
else
{
pushdown(cur);
add(ls, l, mid, L, R, x);
add(rs, mid, r, L, R, x);
pushup(cur);
}
}

Min min(int cur, int l, int r, int L, int R)
{
if (l >= R || r <= L) return Min(N, -1);
if (L <= l && r <= R) return mn[cur];
pushdown(cur);
return merge(min(ls, l, mid, L, R), min(rs, mid, r, L, R));
}

#undef ls
#undef rs
#undef mid
} t;

int n, m, delta, a[N], cnt[N * 3];

int main()
{
scanf("%d%d", &n, &m);

for (int i = 1; i <= n; ++i)
{
scanf("%d", a + i);
++cnt[a[i] + m];
}

const int ll = 1 - m - n, rr = m + n + 2;

t.build(1, ll, rr);

for (int i = 1; i <= n; ++i) t.add(1, ll, rr, i - cnt[i + m] + 1, i + 1, 1);

for (int i = 1; i <= m; ++i)
{
int p, x;
scanf("%d%d", &p, &x);

if (p == 0)
{
if (x == -1)
{
--delta;
t.add(1, ll, rr, n + 1 - cnt[n - delta + m] - delta, n - delta + 1, 1);
}
else
{
t.add(1, ll, rr, n + 1 - cnt[n - delta + m] - delta, n - delta + 1, -1);
++delta;
}
}

else
{
if (a[p] + delta <= n) t.add(1, ll, rr, a[p] - cnt[a[p] + m] + 1, a[p] - cnt[a[p] + m] + 2, -1);
--cnt[a[p] + m];
t.add(1, ll, rr, x - cnt[x - delta + m] - delta, x - cnt[x - delta + m] - delta + 1, 1);
++cnt[x - delta + m];
a[p] = x - delta;
}

Min res = t.min(1, ll, rr, 1 - delta, n - delta + 1);

if (res.val > 0) puts("0");
else printf("%d\n", res.cnt);
}

return 0;
}