首页 > 骚区间
开通博客写题解
头像 范艺杰
发表于 2020-06-27 11:13:29
我们考虑每个点成为区间左端点时合法的右区间范围，我们假定a是下标比i大的且值比i大的最小下标，b是下标比a大且值比i大的最小下标，那么以i为左端点的合法区间范围应是[a, b -1]。同理我们也能求出i是区间右端点时合法的区间[ql, qr]。set即可完成。我们从左往右扫，每个点是左端点时的合法区 展开全文
去ta的博客 赞 (8) 回复(1) 收起
头像 wdyhy
发表于 2020-06-27 09:45:38
E-骚区间题解：这种题首先想到要枚举区间的一个右端点，然后统计有多少合法的左端点。然后我们来求以i作为右端点，左端点在 上时， 作为区间的次大值。那么我们就从左到右枚举右端点，要使 作为次大值，先找到之前出现的离他最近的比他大的数，再找到除了这个比他大的数之外离它最近的比他大的数，就用权值线段树，线 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 18duangduang
发表于 2020-07-07 14:01:07
%参考fyj大佬题解：https://blog.nowcoder.net/n/9eb663297d054e8898236cf06bed7f17分析：骚区间定义：区间左端点为区间的第二小值,区间右端点为区间的第二大值.给定序列是一个1-n的排列,所以无重复元素.求所有骚区间个数.容易想到枚举一个端点， 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

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

扫描二维码，进入QQ群

扫码关注“比赛自动姬”