文章
3
标签
9
分类
2
主页
存档
标签
分类
友链
关于
雪碧的博客
Ciallo~(∠・ω< ) World!
返回首页
主页
存档
标签
分类
友链
关于
Ciallo~(∠・ω< ) World!
发表于
2023-12-06
|
更新于
2026-09-05
|
Daily
|
总字数:
4
|
阅读时长:
1分钟
|
浏览量:
Ciallo~(∠・ω< ) World!
文章作者:
雪碧
文章链接:
https://skd.moe/Daily/ciallo-world/
版权声明:
本博客所有文章除特别声明外,均采用
CC BY-NC-SA 4.0
许可协议。转载请注明来源
雪碧的博客
!
上一篇
求数组任意元素右边第 k 个比它小的元素
Preface 补 Codeforces Round 958 (Div. 2) E 题时,需要求得一个数组任意元素左右第 111 和第 222 个比它小的元素。 研究了 Jiangly 的写法,得到一个通用的解法,记录如下。 问题引入 我们都知道,如果我们想求得一个数组任意元素左边或右边的第一个比他大或小的元素,可以通过单调栈实现,时间和空间复杂度都是 O(n)O(n)O(n) 。但是如果我们想求得一个数组任意元素左边或右边的第 kkk 个比他大或小的元素,该怎么办呢? 解决思路 线段树 + 二分(线段树上二分优化) 我们考虑使用线段树来解决这个问题。我们可以用线段树来维护区间最小值,然后通过二分查找来找到第 iii 个比他小或大的元素的位置,共 kkk 次二分查找,时间复杂度为 O(nklog2n)O(nk\log^2 n)O(nklog2n) 。 考虑线段树上二分优化,可以消去一层二分,时间复杂度为 O(nklogn)O(nk\log n)O(nklogn) 。 这样,我们就得到了时间复杂度为 O(nklogn)O(nk\log n)O(nklogn) 的解法。 但是这...
雪碧
文章
3
标签
9
分类
2
目录
1.
Ciallo~(∠・ω< ) World!
最新文章
欧拉函数学习笔记
2024-10-05
求数组任意元素右边第 k 个比它小的元素
2024-07-17
Ciallo~(∠・ω< ) World!
2023-12-06