首页 > k小数查询
开通博客写题解
头像 SAXYAM
发表于 2021-08-21 09:17:31
B题让我们计算满足 x是区间第K小数的区间个数，就是找有k-1个数小于X的区间。由于区间必定包含X，我们从X开始向左右拓展，计算一下向左/右拓展m个数时对k-1的贡献，存入map计算数量，然后合并左右区间（乘法原理）。答案加上L[d]*R[k-1-d]。别忘记左右单独拓展的贡献，最后特判一下k=1的 展开全文
去ta的博客 赞 (6) 回复(0) 收起
头像 Capture_
发表于 2022-03-15 20:08:31
前缀和求区间 题意：求x是区间第K小数的区间个数，就是找有k-1个数小于X的区间。 我们可以把小于等于x的值的位置由1代替，而大于x的值的位置为0.这样就变成一个 01 序列。 1 ：小于等于x 0 : 大于x 我们设 a[] 为一个前缀和数组，那么我们只需要找到 (区间里1的数量 == k & 展开全文
去ta的博客 赞 (3) 回复(1) 收起
头像 💭💡🎈dear-john
发表于 2021-08-20 23:34:24
B题我们可以预先处理出所有小于 x 的值，给当前位置 pre[i] 加上 1 ，然后处理出前缀和，可以通过前缀和的差值知道每个区间的小于 x 的值的数量，对于 i 位置的pre[i] 一定需要一个pre[i] + k - 1 才能保证该区间的 < x 的数量刚好为k - 1,可以通过二分查找到 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 zzdfw
发表于 2021-08-21 12:11:57
B题https://ac.nowcoder.com/acm/contest/11177/B提供一个我觉得比较清晰的思路，只需要预处理出x两边有多少个数比它小，最后遍历一遍二分查询就行了。 直接拿样例举例：5 3 21 2 3 4 5d[3]=x。我们可以预处理出：l[]={2,1,0,0,0};表示 展开全文
去ta的博客 赞 (2) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

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

扫描二维码，进入QQ群

扫码关注“比赛自动姬”