BJOI2019 删数（贪心，线段树）

题目链接

题意简述

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

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

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

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

修改操作有三种：

单点修改。
全局加一。
全局减一。

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

简要做法

计算数列的权值

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

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

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

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

全局修改

全局修改会导致 $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$。

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

参考代码

#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;
}

文章目录