「SOL」最差记者2 (LOJ / JOISC2016) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

「SOL」最差记者2 (LOJ / JOISC2016)

发表于 分类于 Valine：

一开始思路就想偏了……

# 题面

> Link LOJ #2740

（LOJ 的翻译很清晰了，就不简化了 懒）

# 解析

首先，我们可以考虑只修改 5h 时的榜单中的省份信息。因为所有 2h 和 5h 的选手信息配对完毕后，我们只需要修改 2h 和 5h 的省份信息中的一个。

不妨考虑修改 5h 是的榜单中的省份。那么对于 5h 榜单的每条信息 $(s_1, p_1)$，我们需要将它与 2h 的榜单中的信息 $(s_2,p_2)$ 配对 —— 要求 $s_2\le s_1$。

若配对的 $p_1\neq p_2$，则会产生 $1$ 的修改代价。所以我们应该尽量让省份相同的信息配对。

于是转化成两张榜单信息（称之为「点」）的匹配问题。可以看成是二分图，2h 榜单和 5h 榜单分别是二分图的两个部。

一种贪心想法是按成绩从小到大依次处理 5h 榜单的信息 $(s_1,p_1)$，只考虑与相同省份的信息配对：若存在 2h 榜单的信息 $(s_2,p_2)$（$s_2\le s_1,p_1=p_2$）则取 $\mathbf{s_2}$ 最大的一条信息与 $(s_1,p_1)$ 配对；否则搁置信息 $(s_1,p_1)$，当所有的信息处理完后，再进行完美匹配（无论如何匹配，这些搁置的信息都会产生 $1$ 的修改代价）。

但是这样贪心可能导致最后搁置的信息没有完美匹配。虽然题目保证最初一定有完美匹配，但是在上述贪心过程中，我们贪心地匹配了若干对点，可能导致剩下的点无法匹配。

于是我们简单修补一下这个贪心过程：若存在满足条件的 $(s_2,p_2)$，先尝试与 $(s_1,p_1)$ 配对，检验剩下的点（之前搁置的和尚未处理的）是否有完美匹配，如果有，就匹配。

检验二分图是否有完美匹配，容易想到 Hull 定理。

再加上这张二分图的连边方式非常特殊 —— 5h 榜单的信息 $(s_1,p_1)$ 与所有 2h 榜单中成绩不超过 $s_1$ 的信息（一个前缀）都有连边。

Hull 定理要求「对于“ 5h 部”的每个点集 $S$，其相邻的“ 2h 部”的点集 $T$，必须满足 $|S|\le|T|$」。

根据连边方式，若点集 $S,S’$ 的最大成绩一样，则其相邻的点集 $T$ 就一样 —— 于是我们可以等价地简化条件，对于每个 5h 榜单的前缀点集 $S$，其相邻的点集 $T$ 必须满足 $|S|\le|T|$。这样我们只需检验 $\mathcal{O}(n)$ 个前缀是否满足条件。

再对这个检验过程进行优化 —— 我们把 5h 和 2h 榜单的所有信息放在同一个序列中，按成绩从小到大排序，成绩相同则 2h 榜单的信息靠前。

将序列中 5h 榜单的信息赋值为 $-1$，2h 榜单的信息赋值为 $1$。检验等价于序列的最小前缀和大于等于 $0$。

可以用线段树维护。若检验成功，则匹配 $(s_1,p_1)$ 和 $(s_2,p_2)$，将这两个信息从线段树中删去，也就是将这两个信息的权值覆盖为 $0$。

这样检验后，能在保证合法性（存在完美匹配）的前提下保持最优性。

最后复杂度为 $\mathcal{O}(n\log n)$。

# 源代码

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
/*Lucky_Glass*/
#include <set>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 2e5 + 10;
#define con(type) const type &

int n;
int asco[N], bsco[N], bgrp[N], aref[N], bref[N];
set< pair<int, int> > memb[N];
pair<int, int> sor[N << 1]; // <score, group>

struct SegTree {
	#define idx(l, r) (((l) + (r)) | ((l) != (r)))
	int sum[N << 2], mnpre[N << 2];
	void pushUp(con(int) le, con(int) ri) {
		int mi = (le + ri) >> 1;
		sum[idx(le, ri)] = sum[idx(le, mi)] + sum[idx(mi + 1, ri)];
		mnpre[idx(le, ri)] = min(mnpre[idx(le, mi)], sum[idx(le, mi)] + mnpre[idx(mi + 1, ri)]);
	}
	void build(con(int) le,con(int) ri) {
		if( le == ri ){
			mnpre[idx(le, ri)] = sum[idx(le, ri)] = sor[le].second <= n ? 1 : -1;
			return ;
		}
		int mi = (le + ri) >> 1;
		build(le, mi), build(mi + 1, ri);
		pushUp(le, ri);
	}
	// typ = -1: clear; typ = 1: resume
	void modify(con(int) le, con(int) ri, con(int) pos, con(int) typ) {
		if( le == ri ) {
			if( typ == 1 ) mnpre[idx(le, ri)] = sum[idx(le, ri)] = sor[le].second <= n ? 1 : -1;
			else mnpre[idx(le, ri)] = sum[idx(le, ri)] = 0;
			return;
		}
		int mi = (le + ri) >> 1;
		if( pos <= mi ) modify(le, mi, pos, typ);
		else modify(mi + 1, ri, pos, typ);
		pushUp(le, ri);
	}
	bool query() {return mnpre[idx(1, 2 * n)] >= 0;}
}seg;

int main() {
	// freopen("input.in", "r", stdin);
	scanf("%d", &n);
	for(int i=1,inp;i<=n;i++) {
		scanf("%d%d", &inp, &asco[i]);
		memb[inp].insert(make_pair(asco[i], i));
		sor[i] = make_pair(asco[i], i);
	}
	for(int i=1;i<=n;i++) {
		scanf("%d%d", &bgrp[i], &bsco[i]);
		sor[i + n] = make_pair(bsco[i], i + n);
	}
	sort(sor + 1, sor + 1 + (n << 1));
	for(int i=1;i<=2*n;i++)
		if( sor[i].second > n ) bref[sor[i].second - n] = i;
		else aref[sor[i].second] = i;
	// for(int i=1;i<=2*n;i++) printf("(%d,%d) ", sor[i].first, sor[i].second); printf("\n");
	seg.build(1, n << 1);
	int ans = n;
	for(int i=n;i;i--) {
		set< pair<int, int> >::iterator it = memb[bgrp[i]].lower_bound(make_pair(bsco[i], n + 1));
		if( it != memb[bgrp[i]].begin() ) {
			it--;
			seg.modify(1, n << 1, aref[it->second], -1);
			seg.modify(1, n << 1, bref[i], -1);
			if( !seg.query() ) {
				seg.modify(1, n << 1, aref[it->second], 1);
				seg.modify(1, n << 1, bref[i], 1);
			}
			else {
				ans--;
				memb[bgrp[i]].erase(it);
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}

THE END

Thanks for reading!

暖风捎来馥郁的飘香 栀子花海歆然盛放
我不拒绝对往事回想 也不在乎曾遍体鳞伤
只因为 岁月荏苒 你温柔的目光一如既往
看吧 我将沐火而唱
「一路有你 一路悠扬」

——《我将沐火而唱》By 豆腐P / 东方栀子 / 顾令

> Link 我将沐火而唱 - 网易云