↓Skip to main content
  1. Posts/

AtCoder-ARC189D Takahashi is Slime

·2 mins·
Table of Contents

AtCoder-ARC189D Takahashi is Slime #

Solution 1 #

问题的关键点: 如果小体积的史莱姆体积增大到超过某个相邻的体积更大的史莱姆, 那么它们最终的体积是一样的. 因此, 从大到小考虑. 对于 $a_i$ , 需要计算它第一次能覆盖的范围. 这里需要思考清楚何时使用 $leftGE, rightGE$ , 何时使用 $left, right$ .

能否发生第一波吞并, 取决于 $leftGE$ 和 $rightGE$ (需要 $rightGE_i - leftGE_i \geq 2$) ; 如果有第一波吞并, 那么相同大小的必定能被吞并, 后续吞并应该考虑比自己初始体积大的, 即 $left_i$ 和 $right_i$ .

用单调栈与前缀和可以快速计算.

代码如下:

from collections import defaultdict
from itertools import accumulate

if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))

    left, leftGE, right, rightGE = [0] * n, [0] * n, [0] * n, [0] * n
    st, stGE = [], []
    for i, x in enumerate(a):
        while st and a[st[-1]] <= x:
            st.pop()
        left[i] = -1 if st == [] else st[-1]
        st.append(i)
        while stGE and a[stGE[-1]] < x:
            stGE.pop()
        leftGE[i] = -1 if stGE == [] else stGE[-1]
        stGE.append(i)
    st, stGE = [], []
    for i, x in enumerate(a[::-1]):
        i = n - 1 - i
        while st and a[st[-1]] <= x:
            st.pop()
        right[i] = n if st == [] else st[-1]
        st.append(i)
        while stGE and a[stGE[-1]] < x:
            stGE.pop()
        rightGE[i] = n if stGE == [] else stGE[-1]
        stGE.append(i)

    presum = list(accumulate(a))
    b = sorted([(x, i) for i, x in enumerate(a)], key=lambda x: -x[0])
    ans = [0] * n
    for x, i in b:
        if rightGE[i] - leftGE[i] == 2:
            ans[i] = x
            continue
        nx = presum[right[i] - 1] - (presum[left[i]] if left[i] > -1 else 0)
        ans[i] = nx
        if left[i] > -1 and nx > a[left[i]]:
            ans[i] = max(ans[i], ans[left[i]])
        if right[i] < n and nx > a[right[i]]:
            ans[i] = max(ans[i], ans[right[i]])
    for x in ans:
        print(x, end=' ')
↑