题解 | #哲学家的沉思#
哲学家的沉思
https://ac.nowcoder.com/acm/contest/11175/C
哲学家的沉思
做法1
考虑离线处理,将所有询问挂到区间左端点上。
逆序跑单调栈(递减),假设现在栈顶元素为。此时,对于询问,答案为单调栈内值属于的元素个数。
由于栈顶为,答案为单调栈的某一个后缀。通过二分后缀的起点,就可以以的时间复杂度求解。
单调栈部分共,每一个询问,总的时间复杂度为。
做法2
(以下为口胡
通过单调栈还可以找出对于每一个,他后面第一个大于它的元素。然后问题就可以转化为从可以跳到,问从开始跳,最少几步可以跳到或之后。
现在就是弹飞绵羊,究极经典的题目了,分块或者LCT搞一搞?