首页 > 哲学家的沉思

FutaRian

发表于 2021-06-26 00:19:15

题目要求对一个区间分成最少段，使得每段的最大值都是开头的数。一看到没有修改就想分块暴力预处理乱搞，后来发现没有这么复杂。首先我们肯定从开始找到下一个离它最近的一个比它大的数，然后这中间分成一个段后再以这个数展开全文

Backl1ght

发表于 2021-06-26 11:06:13

哲学家的沉思做法1 考虑离线处理，将所有询问挂到区间左端点上。逆序跑单调栈(递减)，假设现在栈顶元素为。此时，对于询问，答案为单调栈内值属于的元素个数。由于栈顶为，答案为单调栈的某一个后缀。通过二分后缀的起点，就可以以的时间复杂度求解。单调栈部分共，每一个询问，总的时间复杂度为。做法2 （展开全文

查看本题

查看本题讨论

等你来战

查看全部

相关比赛