2013
11-12

# Frequent values

You are given a sequence of n integers a1 , a2 , … , an 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 ai , … , aj.

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.

For each query, print one line with one integer: The number of occurrences of the most frequent value within the given range.

10 3
-1 -1 1 1 1 1 3 10 10 10
2 3
1 10
5 10
0

1
4
3

/* @author: [email protected]/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> *//
import java.io.*;
import java.util.*;
public class Main
{
static  treex[] mytreex=new treex[210000];
static int[] hash=new int[100005];
static int[] left=new int[100005];
static int[] right=new int[100005];
static int[] data=new int[100005];
static boolean build=false;
static int k=0;

public static void main(String args[]) throws Exception
{
String[] ss;
StringBuffer res=new StringBuffer();
while(true)
{
build=false;
int n=Integer.parseInt(ss[0]);
if(n==0)
break;
int q=Integer.parseInt(ss[1]);
k=1;
for(int i=0;i< n;i++)
{
data[i]=Integer.parseInt(ss[i]);
if(i>0&&data[i]!=data[i-1])
{
right[k]=i-1;
left[k+1]=i;
k++;
}
hash[i]=k;
}
right[k]=n-1;
for(int i=0;i< q;i++)
{
int begin=Integer.parseInt(ss[0])-1;
int end=Integer.parseInt(ss[1])-1;
if(hash[begin]==hash[end])
{
res.append(end-begin+1);
res.append("\n");
continue;
}
if(hash[end]-hash[begin]==1)
{
int l=right[hash[begin]]-begin+1;
int r=end-left[hash[end]]+1;
int temp=l>r?l:r;
res.append(temp);
res.append("\n");
continue;

}
if(!build)
{
build=true;
buildtreex(1,k,1);
}
int n1=right[hash[begin]]-begin+1;
int n2=end-left[hash[end]]+1;
if(n1< n2)
n1=n2;
n2=query(hash[begin]+1,hash[end]-1,1);
res.append(n1>n2?n1:n2);
res.append("\n");

}
}
System.out.print(res.toString());
}

public static void buildtreex(int a,int b,int i)
{
if(mytreex[i]==null)
mytreex[i]=new treex();
mytreex[i].left=a;
mytreex[i].right=b;
if(a==b)
mytreex[i].max=right[a]-left[a]+1;
if(a!=b)
{
int mid=(a+b)/2;
buildtreex(a,mid,i*2);
buildtreex(mid+1,b,i*2+1);
mytreex[i].max=mytreex[i*2].max>mytreex[i*2+1].max?mytreex[i*2].max:mytreex[i*2+1].max;
}
}

public static int query(int a,int b,int i)
{
if(a==mytreex[i].left&&b==mytreex[i].right)
return mytreex[i].max;
int mid=(mytreex[i].left+mytreex[i].right)/2;
if(b<=mid)
return query(a,b,2*i);
else if(a>=mid+1)
return query(a,b,2*i+1);
else
{
int l =query(a,mid,2*i);
int r = query(mid+1,b,2*i+1);
return l>r?l:r;
}
}

}

class treex
{
int left;
int right;
int max;
}

1. 题本身没错，但是HDOJ放题目的时候，前面有个题目解释了什么是XXX定律。
这里直接放了这个题目，肯定没几个人明白是干啥