首页 > King of Range
开通博客写题解
头像 QQQQQQ5292
发表于 2021-08-01 15:10:04
题目描述：题目给你一个长度为n的序列，m次询问，每次询问给一个k，寻找有多少个区间【l，r】满足区间内的数组最大值减数组最大值大于k（不等于k）思路分析：我们给定一个i，为满足条件的区间左边界。然后往后找右区间边界，我们令j为区间右边界，而我们只需要找出这个区间内满足条件的最小j即可，因为这个j后面 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 河南老乡唐可可
发表于 2021-08-11 14:08:23
题目大意 给定一个个数的序列。有次询问，每次询问是一个非负整数，求出有多少对，满足,其中。 思路 不难发现满足要求的序列有单调性，即如果当前区间满足最大值减去最小值大于k，那么包含这个区间的更大的区间，也一定满足。 而这一类问题，通常可以采用尺取法。即： 我们先固定起点，然后让从开始一个一个往后走 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 sunrise__sunrise
发表于 2021-08-23 15:44:27
题目大意 给你长度为的序列，并且有次查询，每次查询给出一个，询问在中有多少个区间的最大值减掉最小值严格大于。 Solution 考点：双指针+表 考虑到区间不会修改，那么查找区间最值这个问题就用表维护就可以。 然后再看最大值减掉最小值严格大于，如果在这个区间符合要求，那么是不是在这些右区间都是合法的 展开全文
去ta的博客 赞 (1) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

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

扫描二维码，进入QQ群

扫码关注“比赛自动姬”