P2824 排序 线段树 + 二分
发布日期:2021-09-25 23:58:01
浏览次数:18
分类:技术文章
本文共 2367 字,大约阅读时间需要 7 分钟。
比较有意思的一个题。 直接排序肯定是不可以的。那看最后询问,只是一个位置,那说明是一个确定的值 x 。可以考虑讲原序列转换成01序列,>= x 的为1 ,< x 的为0,用线段树维护区间内1的值。那么排序的操作即可转换成对区间内01两个数的操作。假如当前区间为 [ l , r ] ,1 的个数为 cnt 。如果要升序的话,只需要 modify(1,r,r-cnt+1,1) 和 modify(1,l,r-cnt,0) 即可 ,也就是把 [ r , r - cnt + 1 ] 改成 1 ,把 [ l , r - cnt ] 改成 0 。降序同理。这样就可以做到 log(n) 排序了。 下面考虑怎么得到第 q 位置上的数。 显然是存在一个单调性的。当 q 位置上的数是 1 的话,ans = mid l = mid + 1 ,是 0 的话 r = mid - 1 。这样二分出来答案即可。#include#include #include #include #include
转载地址:https://blog.csdn.net/DaNIelLAk/article/details/108270958 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
网站不错 人气很旺了 加油
[***.192.178.218]2024年04月16日 21时15分00秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
【Leetcode刷题篇】leetcoe109 有序链表转换二叉搜索树
2019-04-26
【Leetcode刷题篇】leetcode938 二叉搜索树的范围和
2019-04-26
【Leetcode刷题篇】leetcode235 二叉搜索树的最近公共祖先
2019-04-26
【Leetcode刷题篇】leetcode236 二叉树的最近公共祖先
2019-04-26
【Leetcode刷题篇】leetcode230 二叉搜索树中第K小的元素
2019-04-26
【Leetcode刷题篇】leetcode173 二叉搜索树迭代器
2019-04-26
【Leetcode刷题篇】leetcode99 恢复二叉搜索树
2019-04-26
【Leetcode刷题篇】leetcode451根据字符出现频率排序
2019-04-26
【Leetcode刷题篇】leetcode703 数据流中的第k大元素
2019-04-26
【Leetcode刷题篇】leetcode378 有序矩阵中第K小的元素
2019-04-26
【Leetcode刷题篇】前K个高频元素
2019-04-26
【Leetcode刷题篇】leetcode373 查找和最小的K对数字
2019-04-26
【Leetcode刷题篇】leetcode367 有效的完全平方数
2019-04-26
【Leetcode刷题篇】剑指offer-数值的整数次方
2019-04-26
【Leetcode刷题篇】面试题01.06 字符串压缩
2019-04-26
【Leetcode刷题篇】leetcode443 压缩字符串
2019-04-26
【面试篇】数据结构-线性表
2019-04-26
【面试篇】数据结构-树形结构
2019-04-26
【面试篇】数据结构-哈希表
2019-04-26
【Leetcode刷题篇】leetcode88 合并两个有序数组
2019-04-26