题意/Description：
给一个长度为n的不降序列a1,a2,a3,…,an,有q个询问，每个询问为:
i j
询问在子序列ai…aj中出现最多的元素。
数据范围：1 <= n, q <= 100000
读入/Input：
The input consists of several test cases. Each test case starts with a line containing two integers n and q (1 ≤ n, q ≤ 100000). The next line contains n integers a1 , ... , an (-100000 ≤ ai ≤ 100000, for each i ∈ {1, ..., n}) separated by spaces. You can assume that for each i ∈ {1, ..., n-1}: ai ≤ ai+1. The following q lines contain one query each, consisting of two integers i and j (1 ≤ i ≤ j ≤ n), which indicate the boundary indices for the query.
The last test case is followed by a line containing a single 0.
输出/Output：
For each query, print one line with one integer: The number of occurrences of the most frequent value within the given range.
题解/solution：
注意到题目描述中的“不降序列”，让我们联想到可以使用线段树这一数据结构。
在线段树的结点内设5个变量l、r、fmax、fl、fr，[l,r]表示该结点的区间范围，lf和rf分别表示元素a[l]和a[r]在区间内的出现频率，fmax表示区间内的最高出现频率。
假设区间[x,y]和[y+1,z]均被询问[i,j]覆盖，则可以分情况讨论区间[x,z]的fmax值：
若a[y]==a[y+1]，则fmax[x,y]=max{fmax[x,y],fmax[y+1,z],rf[x,y]+lf[y+1,z]}
否则fmax[x,y]=max{fmax[x,y],fmax[y+1,z]}
代码/Code：
type
arr=record
l,r:longint;
fl,fr,fmax:longint;
end;
var
tree:array [0..300001] of arr;
a:array [0..100001] of longint;
n,m:longint;
function min(o,p:longint):longint;
begin
if o<p then exit(o);
exit(p);
end;
procedure ins(p,b,e:longint);
var
m:longint;
begin
tree[p].l:=b; tree[p].r:=e;
if (b=e) then
begin
tree[p].fl:=1;
tree[p].fr:=1;
tree[p].fmax:=1;
exit;
end;
m:=(b+e) shr 1;
ins(p*2,b,m);
ins(p*2+1,m+1,e);
tree[p].fl:=tree[p*2].fl;
tree[p].fr:=tree[p*2+1].fr;
if a[tree[p*2].r]=a[tree[p*2+1].l] then
begin
tree[p].fmax:=tree[p*2].fr+tree[p*2+1].fl;
if a[tree[p].r]=a[tree[p*2+1].l] then
tree[p].fr:=tree[p].fmax;
if a[tree[p].l]=a[tree[p*2].r] then
tree[p].fl:=tree[p].fmax;
end else tree[p].fmax:=1;
if tree[p*2].fmax>tree[p].fmax then
tree[p].fmax:=tree[p*2].fmax;
if tree[p*2+1].fmax>tree[p].fmax then
tree[p].fmax:=tree[p*2+1].fmax;
end;
function count(p,b,e:longint):longint;
var
max1,max2:longint;
begin
with tree[p] do
begin
if (b<=l) and (e>=r) then exit(fmax);
if e<=tree[p*2].r then
exit(count(p*2,b,e));
if b>=tree[p*2+1].l then
exit(count(p*2+1,b,e));
count:=1;
if a[tree[p*2].r]=a[tree[p*2+1].l] then
count:=min(tree[p*2].r-b+1,tree[p*2].fr)+min(e-tree[p*2+1].l+1,tree[p*2+1].fl); // 询问区间有可能未把tree[p*2].fr个元素全包含进去，所以要取min(tree[p*2].r-b+1, tree[p*2].fr)
max1:=count(p*2,b,tree[p*2].r);
max2:=count(p*2+1,tree[p*2+1].l,e);
if max1>count then count:=max1;
if max2>count then count:=max2;
end;
end;
procedure main;
var
i,x,y:longint;
begin
while 1=1 do
begin
read(n);
if n=0 then exit;
readln(m);
for i:=1 to n do
read(a[i]);
ins(1,1,n);
for i:=1 to m do
begin
readln(x,y);
writeln(count(1,x,y));
end;
end;
end;
begin
main;
end.