学步园

【题意】

给定一段长度N不减数字序列，询问M次某一段之间最多出现相同的数字多少个

【输入】

多组数据

第一行两个数字n,m（均小于100000）

每组数据第一行为n个数字表示序列

接下来m行每行为两个数字l，r表示询问

数据以单独一行的一个0结束

【输出】

对于每组数据的每次询问，输出一个数字表示该段中最多出现相同的数字多少个

ST算法，我看的是discuss中的解析……

需要注意的k=trunc(ln(b-a+1)/ln(2))

program poj3368;
var
  n,m,i,j,k,tot,a,b,ans:longint;
  p,belong,pos,long:array [0..100001] of longint;
  max:array [0..18,0..100001] of longint;

function similar (a,b:longint):longint;
var
  k:longint;
begin
  if a=b then exit(long[a]);
  k:=trunc(ln(b-a+1)/ln(2));
  if max[k,a]>max[k,b-(1 shl k)+1] then exit(max[k,a])
                                   else exit(max[k,b-(1 shl k)+1]);
end;

begin
  repeat
    read(n);
    if n=0 then break;
    read(m);
    for i:=1 to n do
      read(p[i]);
    k:=p[1];
    tot:=1;
    fillchar(long,sizeof(long),0);
    for i:=1 to n do
      begin
        if p[i]<>k then
          begin
            k:=p[i];
            inc(tot);
          end;
        belong[i]:=tot;
        inc(long[tot]);
        pos[i]:=long[tot];
      end;
    for i:=1 to tot do
      max[0,i]:=long[i];
    k:=0;
    while 1 shl k < tot do
      begin
        for i:=1 to tot do
          if i+(1 shl k)>tot then max[k+1,i]:=max[k,i]
                           else
          if max[k,i]>max[k,i+(1 shl k)] then max[k+1,i]:=max[k,i]
                                         else max[k+1,i]:=max[k,i+(1 shl k)];
        inc(k);
      end;
    for i:=1 to m do
      begin
        read(a,b);
        if belong[a]=belong[b] then
          begin
            writeln(b-a+1);
            continue;
          end;
        if long[belong[a]]-pos[a]+1>pos[b] then ans:=long[belong[a]]-pos[a]+1
                                           else ans:=pos[b];
        if belong[a]+1<=belong[b]-1 then k:=similar(belong[a]+1,belong[b]-1)
                                    else k:=0;
        if k>ans then ans:=k;
        writeln(ans);
      end;
  until false;
end.