poj 3368 Frequent values (暴力+rmq,分类讨论)

poj 3368 题目链接

题意:给出n个非减的数a[i],求区间[l,r]中出现次数最多的数的出现的次数。

思路:由于数列非减,那么相等的数一定相邻。很容易系哪个到构造另一个数组f[i],表示从当前位置向左边延伸最多延伸几个相等的数。

f[i] = f[i-1] + 1 (iff[……]

Read more