题解：区间最大频率查询

这道题要求在非递减序列中查询区间内出现次数最多的数值的频率。由于序列非递减，相同数值会连续出现，因此可以预处理每个位置的连续出现次数，并使用RMQ（Range Maximum Query）算法高效查询区间最大值。

解决代码

import sys
import math

def main():
    input = sys.stdin.read().split()
    ptr = 0
    while True:
        n = int(input[ptr])
        ptr += 1
        if n == 0:
            break
        q = int(input[ptr])
        ptr += 1
        arr = list(map(int, input[ptr:ptr+n]))
        ptr += n
        
        # 预处理每个位置的连续出现次数
        s = [1] * n
        for i in range(1, n):
            if arr[i] == arr[i-1]:
                s[i] = s[i-1] + 1
            else:
                s[i] = 1
        
        # 预处理RMQ表
        logn = math.floor(math.log2(n)) if n > 0 else 0
        rmq = [[0] * (logn + 1) for _ in range(n)]
        for i in range(n):
            rmq[i][0] = s[i]
        for k in range(1, logn + 1):
            for i in range(n - (1 << k) + 1):
                rmq[i][k] = max(rmq[i][k-1], rmq[i + (1 << (k-1))][k-1])
        
        # 处理查询
        for _ in range(q):
            l = int(input[ptr]) - 1  # 转换为0-based
            ptr += 1
            r = int(input[ptr]) - 1
            ptr += 1
            
            # 找到左端点所在连续段的末尾
            cnt = l
            while cnt < r and arr[cnt] == arr[cnt + 1]:
                cnt += 1
            
            # 计算左端点所在段的贡献
            left_count = cnt - l + 1
            
            # 剩余区间的最大值
            remaining_max = 0
            if cnt + 1 <= r:
                a = cnt + 1
                b = r
                length = b - a + 1
                k = 0
                while (1 << (k + 1)) <= length:
                    k += 1
                remaining_max = max(rmq[a][k], rmq[b - (1 << k) + 1][k])
            
            print(max(left_count, remaining_max))

if __name__ == "__main__":
    main()

这种方法通过预处理将查询复杂度优化到O(1)，适用于大规模数据的高效查询。