uva11235区间众数FrequentvaluesST表分块,众数区间分步

题目描述

题目链接←戳我
给出一个非递减数列，多次查询，每次查询一个区间内 出现次数最多的数 的出现次数（中文小心被绕进去，原题的英文还是很好理解的）

题目分析

应用分块的思想，把数字相同的分为一块，cnt[i]表示第i块中数字的个数，L[i]表示第i块的下标左边界，R[i]表示第i块的下标右边界(均为闭区间)，bel[i]表示第i个数字属于第几块，使用ST表预处理区间cnt的最大值
           -1 -1 1 1 1 1 3 10 10 10
cnt[times]   2      4    1    3
L[i]         1      3    7    8
R[i]         2      6    7    10
则区间[l,r]的答案为
R[bel[l]]-l+1
r-L[bel[r]]+1
第bel[l]+1块到bel[r]-1块的cnt[i]的最大值
这三者中的最大值

代码参考 /* * @Author: CHAOS_ORDER * @Date: 2019-09-14 14:58:21 * @LastEditors: CHAOS_ORDER * @LastEditTime: 2019-09-17 16:43:21 * @Description: C - Frequent values http://acm.hdu.edu.cn/showproblem.php?pid=1806 * @Status: Accepted 280ms */#include #include #include #include #include #include #include #include #include #include #include #include #include #include