poj3368 Frequent values（线段树）

Description

You are given a sequence of n integers a₁ , a₂ , ... , a_n in non-decreasing order. In addition to that, you are given several queries consisting of indices i and j (1 ≤ i ≤ j ≤ n). For each query, determine the most frequent value among the integers a_i , ... , a_j.

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 a₁ , ... , a_n (-100000 ≤ a_i ≤ 100000, for each i ∈ {1, ..., n}) separated by spaces. You can assume that for each i ∈ {1, ..., n-1}: a_i ≤ a_i+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.

Sample Input

10 3

-1 -1 1 1 1 1 3 10 10 10

2 3

1 10

5 10

0

Sample Output

Source

Ulm Local 2007

无脑的线段树。写着玩玩。

 program rrr(input,output);

 type

   treetype=record

      l,r,m,lm,rm:longint;

   end;

 var

   a:array[..]of treetype;

   c:array[..]of longint;

   n,i,q,x,y:longint;

 function max(a,b:longint):longint;

 begin

    if a>b then exit(a) else exit(b);

 end;

 function min(a,b:longint):longint;

 begin

    if a<b then exit(a) else exit(b);

 end;

 procedure build(k,l,r:longint);

 var

   mid,i:longint;

 begin

    a[k].l:=l;a[k].r:=r;

    if l=r then begin a[k].m:=;a[k].lm:=;a[k].rm:=;exit; end;

    mid:=(l+r)>>;i:=k+k;

    build(i,l,mid);build(i+,mid+,r);

    a[k].m:=max(a[i].m,a[i+].m);if c[mid]=c[mid+] then a[k].m:=max(a[k].m,a[i].rm+a[i+].lm);

    if c[l]=c[mid+] then a[k].lm:=a[i].lm+a[i+].lm else a[k].lm:=a[i].lm;

    if c[mid]=c[r] then a[k].rm:=a[i].rm+a[i+].rm else a[k].rm:=a[i+].rm;

 end;

 function query(k:longint):longint;

 var

   mid,i,ans:longint;

 begin

     if (x<=a[k].l) and (a[k].r<=y) then exit(a[k].m);

     mid:=(a[k].l+a[k].r)>>;i:=k+k;

     ans:=;

     if x<=mid then ans:=query(i);

     if mid<y then ans:=max(ans,query(i+));

     if (x<=mid) and (mid<y) and (c[mid]=c[mid+]) then ans:=max(ans,min(mid-x+,a[i].rm)+min(y-mid,a[i+].lm));

     exit(ans);

 end;

 begin

    assign(input,'r.in');assign(output,'r.out');reset(input);rewrite(output);

    while true do

       begin

          read(n);if n= then break;

          readln(q);

          for i:= to n do read(c[i]);

          build(,,n);

          for i:= to q do begin readln(x,y);writeln(query()); end;

       end;

    close(input);close(output);

 end.

巴特西

poj3368 Frequent values（线段树）

最新文章

热门文章