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