POJ 2796 – Feel Good

题目链接:POJ – 2796

这是一个典型问题:需要你在短时间内求出所有的点左边/右边第一个比它大/小的位置。

应用:2019牛客多校第四场C计蒜客38228 – Max answer

方法一:利用已经得到的信息转移

以找到某个点左边/右边第一个比它小的位置为例(这里不包括那个比它小的点):

当$a(i) < a(l_i – 1) $时,$l_i = l_{l_i – 1} $,直到满足$a(i) < a(l_i – 1) $。

当$a(i) > a(r_i + 1)$时,$r_i = r_{r_i + 1} $,直到满足$a(i) > a(r_i + 1)$。

初始化$a_0 = a_{n+1} = -\infty$,保证不会越界。

方法二:单调栈

维护一个单调栈,单调栈的顶部是左边/右边第一个比当前点小的点,如果需要不包含这个点,则左边+1右边-1即可。

 

说点什么

avatar
50
  Subscribe  
提醒