首页 > 哲学家的沉思
开通博客写题解
头像 FutaRian
发表于 2021-06-26 00:19:15
题目要求对一个区间分成最少段，使得每段的最大值都是开头的数。 一看到没有修改就想分块暴力预处理乱搞，后来发现没有这么复杂。 首先我们肯定从 开始找到下一个离它最近的一个比它大的数，然后这中间分成一个段后再以这个数 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 Backl1ght
发表于 2021-06-26 11:06:13
哲学家的沉思 做法1 考虑离线处理，将所有询问挂到区间左端点上。 逆序跑单调栈(递减)，假设现在栈顶元素为。此时，对于询问，答案为单调栈内值属于的元素个数。 由于栈顶为，答案为单调栈的某一个后缀。通过二分后缀的起点，就可以以的时间复杂度求解。 单调栈部分共，每一个询问，总的时间复杂度为。 做法2 （ 展开全文
去ta的博客 赞 (0) 回复(2) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”