首页 > Neat Tree
开通博客写题解
头像 白色L号谢谢
发表于 2020-07-13 17:50:11
可以分开计算，先计算所有区间内的最大值之和，再减去所有区间的最小值之和。 #include <iostream> #include <stdio.h> #include <string.h> #include <time.h> #include &l 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 回归梦想
发表于 2020-09-07 19:56:50
Neat Tree 题意： n个数，每个区间的贡献为区间内最大值减最小值，问这个n个数的总贡献是多少？也就是n所能组成的所有区间的贡献值之和 题解： 我们可以用单调栈来做第i个数对答案的贡献值为=h[i] * 作为最大值出现的次数-h[i] * 作为最小值出现的次数求每个点贡献值的过程可以用单调栈来 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 苟且的狮子
发表于 2021-03-13 10:34:18
单调栈 单调栈接触挺久了，一直没有仔细研究。昨天模拟赛，一道单调栈没有看出来。现在认真学学！ 对于这道题，因为它是连续子序列所以我们可以统计每一个值的贡献即，(作为最大值的次数-作为最小值的次数)*高度 如何求作为最大值的次数？我们可以求解，向左走第一个比他大的索引，向右走第一个比他大的索引那么，在 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

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

扫描二维码，进入QQ群

扫码关注“比赛自动姬”