[eJOI 2020] Fountain (Day1)

题意

水从指定圆盘开始，装满后流向下方第一个直径更大的圆盘。每次询问互不影响，求给定水量最后停在哪个圆盘；流出喷泉则输出 0。

思路

每个圆盘的后继是它右侧第一个直径严格更大的圆盘。用单调递减栈线性求出 next_larger，并增加编号 n 作为流出喷泉的哨兵。

水只会沿这棵“后继森林”向下走。倍增表维护：

jump[level][i]：从 i 越过 $2^{level}$ 个圆盘后的位置；
total[level][i]：越过这些圆盘需要装满的总容量。

回答询问时从大层向小层尝试。只有 total < water 才会真正溢出这些圆盘；若水量恰好等于容量，水停在最后一个被装满的圆盘，因此不能写成 <=。

Python 知识

普通 list 很适合实现单调栈，append/pop 都是均摊 $O(1)$ 。
array("i") 和 array("q") 分别紧凑保存 32 位下标与 64 位容量和，避免 Python 整数表造成过高内存。
n.bit_length() 直接给出倍增所需层数。
多个答案先收集，再用 "\n".join(answers) 一次输出。

代码

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
36import sys
from array import array


data = iter(map(int, sys.stdin.buffer.read().split()))
n, queries = next(data), next(data)
diameter = array("q", [0]) * n
capacity = array("q", [0]) * (n + 1)
for i in range(n):
    diameter[i], capacity[i] = next(data), next(data)

next_larger = array("i", [n]) * (n + 1)
stack = []
for i, value in enumerate(diameter):
    while stack and diameter[stack[-1]] < value:
        next_larger[stack.pop()] = i
    stack.append(i)

levels = n.bit_length() + 1
jump = [next_larger]
total = [capacity]
for _ in range(1, levels):
    previous_jump, previous_total = jump[-1], total[-1]
    jump.append(array("i", (previous_jump[previous_jump[i]] for i in range(n + 1))))
    total.append(array("q", (previous_total[i] + previous_total[previous_jump[i]]
                             for i in range(n + 1))))

answers = []
for _ in range(queries):
    current, water = next(data) - 1, next(data)
    for level in range(levels - 1, -1, -1):
        if current < n and total[level][current] < water:
            water -= total[level][current]
            current = jump[level][current]
    answers.append(str(current + 1 if current < n else 0))
print("\n".join(answers))

复杂度

单调栈预处理 $O(n)$ ，倍增预处理 $O(n\log n)$ ；每次询问 $O(\log n)$ 。空间 $O(n\log n)$ 。

总结

先用单调栈把几何描述化成唯一后继，再把“沿后继链走多远”交给倍增，是这类题的通用组合。

[eJOI 2020] Fountain (Day1)

目录

题意

思路

Python 知识

代码

复杂度

总结