首页 > 蒲公英
开通博客写题解
头像 19-大数据一班-杨文冠
发表于 2020-12-11 12:31:12
思路：注意输入的的意思，强制在线处理。求一个区间的众数不具有区间“区间可加性”，树状数组和线段树去维护非常困难，而分块大段维护、局部朴素就非常的适合。看完题解自己在实现有点难度，蓝书就点拨一下，不给多余提示。 这题是要用到桶的，所以先把出现的离散化到自然数上。将序列分成段，每段的长度为，不一定要是， 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 可爱哈姆
发表于 2021-10-27 15:10:52
思路： 区间众数很容易想到莫队，但本题要求强制在线，莫队的在线化实现相当复杂，故采用分块。 先将a序列离散化，然后用朴素的方法处理出各大块之间的众数是多少。关于残块，不难发现众数只可能是残块中的数或大块间众数，故只需再统计各块中各数字出现次数，每次处理询问时比较至多 2S+12S+12S+1 个数的 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 henry_y
发表于 2019-09-02 21:22:55
因为太菜所以只会的做法 就是那种要用二分的，并不会clj那种不带log的做法 首先数的值域为1e9肯定要离散化一下 因为数最多有40000个所以开40000个vector，存一下每个数出现的位置 预处理出每个以块的端点为左右端点的区间的众数，这种区间一共有O(block^2)个，所以可以用O(n*b 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

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

扫描二维码，进入QQ群

扫码关注“比赛自动姬”