[JOISC 2021] Event Hopping 2

GitHub 跳转原题关系图返回列表

按编号做字典序贪心，以区间调度倍增作为可扩展性判定，并用 Treap 维护空闲时间段。

OJ: luogu

题目 ID: P7562

难度:NOI/NOI+/CTSC

标签:字典序贪心倍增Treappython

日期: 2026-07-16 18:28

题意

从按编号给出的活动中选择恰好 k 个两两不冲突的活动。若可行，输出编号递增且字典序最小的方案。

思路

依次扫描活动编号。若当前活动与已选活动兼容，并且选它之后仍能补足剩余数量，就立刻选择；这是构造字典序最小序列的标准“能选则选”。难点是快速判断“还能选多少个”。

对任意空闲时间段 [left, right]，最多活动数由经典区间调度贪心得到：每次选择开始不早于当前位置且结束最早的活动。离散化端点后，next_end[x] 表示这一步会到达的最早结束坐标；对它建立倍增，query(left, right) 就能在 $O(\log n)$ 内计算最多可放活动数。

已选活动把时间轴切成若干互不相交的空闲段，总可选数是各段 query 之和。尝试加入 [L,R] 时，只需把它所在空闲段的贡献替换为 [free_left,L] 与 [R,free_right] 两段的贡献。

空闲段需要按左端点查询前驱、删除和插入，代码用随机 Treap 维护。若新的总容量仍不少于所需活动数，就正式选择当前编号并分裂空闲段。

Python 知识

集合推导式收集所有端点，sorted 加 bisect_left 完成离散化。
array("i") 保存倍增表，在 n=10^5 时比整数列表节省很多内存。
Treap 的左右儿子、优先级、键和值分别存在列表中，用整数编号代替大量节点对象。
固定 random.seed(...) 使随机树形可复现；期望复杂度仍为对数级。
"\n".join(map(str, chosen)) 一次输出选择序列。

代码

python

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
132import random
import sys
from array import array
from bisect import bisect_left


data = iter(map(int, sys.stdin.buffer.read().split()))
n, required = next(data), next(data)
events = [(next(data), next(data)) for _ in range(n)]
coordinates = sorted({value for event in events for value in event})
compressed = [(bisect_left(coordinates, left), bisect_left(coordinates, right))
              for left, right in events]
coordinate_count = len(coordinates)

next_end = array("i", [coordinate_count]) * (coordinate_count + 1)
for left, right in compressed:
    if right < next_end[left]:
        next_end[left] = right
for i in range(coordinate_count - 1, -1, -1):
    if next_end[i + 1] < next_end[i]:
        next_end[i] = next_end[i + 1]

jump = [next_end]
for _ in range(1, n.bit_length() + 1):
    previous = jump[-1]
    jump.append(array("i", map(previous.__getitem__, previous)))


def query(left, right):
    count = 0
    current = left
    for level in range(len(jump) - 1, -1, -1):
        destination = jump[level][current]
        if destination <= right:
            current = destination
            count += 1 << level
    return count


# Randomized treap of disjoint free intervals, keyed by left endpoint.
random.seed(20260716)
left_child = [0]
right_child = [0]
priority = [0]
key = [0]
value = [0]


def new_node(left, right):
    left_child.append(0)
    right_child.append(0)
    priority.append(random.randrange(1 << 30))
    key.append(left)
    value.append(right)
    return len(key) - 1


def split(root, split_key):
    if not root:
        return 0, 0
    if key[root] < split_key:
        left_tree, right_tree = split(right_child[root], split_key)
        right_child[root] = left_tree
        return root, right_tree
    left_tree, right_tree = split(left_child[root], split_key)
    left_child[root] = right_tree
    return left_tree, root


def merge(left_root, right_root):
    if not left_root or not right_root:
        return left_root or right_root
    if priority[left_root] < priority[right_root]:
        right_child[left_root] = merge(right_child[left_root], right_root)
        return left_root
    left_child[right_root] = merge(left_root, left_child[right_root])
    return right_root


def insert(root, node):
    if not root or priority[node] < priority[root]:
        left_child[node], right_child[node] = split(root, key[node])
        return node
    if key[node] < key[root]:
        left_child[root] = insert(left_child[root], node)
    else:
        right_child[root] = insert(right_child[root], node)
    return root


def erase(root, target_key):
    if key[root] == target_key:
        return merge(left_child[root], right_child[root])
    if target_key < key[root]:
        left_child[root] = erase(left_child[root], target_key)
    else:
        right_child[root] = erase(right_child[root], target_key)
    return root


def predecessor(root, target_key):
    result = 0
    while root:
        if key[root] <= target_key:
            result = root
            root = right_child[root]
        else:
            root = left_child[root]
    return result


root = new_node(0, coordinate_count - 1)
available = query(0, coordinate_count - 1)
chosen = []

for identity, (event_left, event_right) in enumerate(compressed, 1):
    node = predecessor(root, event_left)
    if not node or value[node] < event_right:
        continue
    free_left, free_right = key[node], value[node]
    remaining = (available - query(free_left, free_right)
                 + query(free_left, event_left) + query(event_right, free_right))
    if remaining >= required - len(chosen) - 1:
        chosen.append(identity)
        available = remaining
        root = erase(root, free_left)
        root = insert(root, new_node(free_left, event_left))
        root = insert(root, new_node(event_right, free_right))
        if len(chosen) == required:
            break

print("\n".join(map(str, chosen)) if len(chosen) == required else -1)

复杂度

离散化、倍增和逐活动判定共 $O(n\log n)$ 期望时间。倍增表占 $O(n\log n)$ 空间，Treap 与其他数组占 $O(n)$ 。

总结

字典序贪心本身只有一句“能选则选”，真正的工程核心是提供快速的可扩展性判定：区间调度倍增计算容量，Treap 维护被已选活动切开的空闲段。

P7562 [JOISC 2021] イベント巡り 2 (Event Hopping 2) (Day4)

题目背景

如果无法在洛谷下载测试数据，可以点此下载所有数据。

题目描述

IOI Park 将有 $n$ 场活动。

这些活动的编号从 $1$ 到 $n$ 。活动 $i$ 从时间 $L_i+10^{-1}$ 到时间 $R_i-10^{-1}$ 举行。数据保证 $L_i$ 和 $R_i$ 是整数。

JOI 君决定参加其中的 $k$ 个活动。但是，JOI 君不能在中间加入或离开每个活动。在两个活动场所间移动的时间忽略不计。

JOI 君希望参加编号较小的活动。严格来说，JOI 君参加的 $k$ 个活动的编号依次为 $a_1,\cdots,a_k$ ，其中 $1 \le a_1 < \cdots < a_k \le n$ 。如果序列 $(a_1, \cdots, a_k)$ 的编号小于 $(b_1, \cdots, b_k)$ ，当且仅当存在 $j\ (1 \le j \le k)$ 满足在区间 $[1,j-1]$ 里的所有 $l$ 都有 $a_l=b_l$ 和 $a_j<b_j$ 。

给出每个活动的信息和 JOI 君参加的活动个数 $k$ ，判断 JOI 君是否可以参加 $k$ 个活动，如果可以，输出所有的 $k$ 个活动的编号。

输入格式

第一行，两个正整数 $n,k$ 。

第 $2 \sim n + 1$ 行，每行 $2$ 个正整数， $L_i, R_i$ 。

输出格式

如果 JOI 君可以参加 $k$ 个活动：

输出 $k$ 行。
我们设 JOI 君参与的 $k$ 个活动的编号为 $a_1, a_2, \cdots, a_k\ (1\le a_1 < \cdots < a_k \le n）$ ，你需要在第 $j$ 行输出 $a_j\ (1\le j \le k)$ 。请注意，序列 $(a_1, \cdots, a_k)$ 必须是 最小字典序。

如果 JOI 君无法参加 $k$ 个活动，输出 $\texttt{-1}$ 。

输入输出样例 #1

输入 #1

text

输出 #1

text

输入输出样例 #2

输入 #2

text

输出 #2

text

1-1

输入输出样例 #3

输入 #3

text

1
2
3
4
5
6
7
8
9
10
1110 6
77412002 93858605
244306432 318243514
280338037 358494212
439397354 492065507
485779890 529132783
571714810 632053254
659767854 709114867
718405631 733610573
786950301 815106357
878719468 899999649

输出 #3

text

输入输出样例 #4

输入 #4

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2120 16
250732298 258217736
26470443 34965880
252620676 260043105
692063405 697656580
497457675 504191511
391372149 397942668
858168758 867389085
235756850 241022021
585764751 593366541
207824318 217052204
661682908 671226688
886273261 892279963
770109416 778960597
264372562 270395107
176883483 186662376
509929119 519063796
109491630 118520141
162731982 168101507
662727316 668317158
757072772 765493222

输出 #4

text

说明/提示

样例 #1 解释

有 $2$ 种方式可以参加正好 $4$ 个活动。

参加 $1, 3, 4, 5$ ；
参加 $2, 3, 4, 5$ 。

数列 $(1,3,4,5)$ 比数列 $(2, 3, 4, 5)$ 字典序小，所以输出 $1, 3, 4, 5$ 。

样例 #2 解释

无论怎么选择都不可能正好参加 $3$ 个活动，所以输出 $\tt -1$ 。

样例 #3 解释

本样例满足所有 Subtask 的条件。

数据规模与约定

因洛谷限制，本题不予评测每个 Subtask 的第 $1\sim 20$ 个测试点。

本题采用 Subtask 计分法。

Subtask	分值占比百分率	$n$	$L_i$
$1$	$7\%$	/	$L_i \le L_{i+1}\ (1 \le i \le n − 1)$
$2$	$1\%$	$\le20$	/
$3$	$31\%$	$\le 3 \times 10^3$	/
$4$	$61\%$	/	/

注：斜线表示无特殊限制。

对于 $100\%$ 的数据：

$1\le n\le 10^5$ ；
$1 \le k \le n$ ；
$1\le L_i < R_i \le 10^9 (1\le i \le n)$ 。

说明

本题译自第２０回日本情報オリンピック 2020/2021春季トレーニング合宿 - 競技 4 - T1 日文题面。

[JOISC 2021] Event Hopping 2

目录

题意

思路

Python 知识

代码

复杂度

总结