Frequent values Time Limit: 2000MS Memory Limit: 65536KTotal Submissions: 7310 Accepted: 2617
Description
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.
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.
Sample Input
10 3 -1 -1 1 1 1 1 3 10 10 10 2 3 1 10 5 10 0Sample Output
1 4 3Source
Ulm Local 2007 #include<cstdio> #include<cstring> #include<cmath> #define mmax(a,b) ((a)>(b)?(a):(b)) const int MAXN=100000+10; int a[MAXN],hash[MAXN]; int f1[MAXN][20]; int t,n; struct Point { int left,right; int count,num; } point[MAXN]; void init() //离散化，相同的点缩成一点，记录区间左端点，右端点，出现次数，和数字 { point[0].num=a[0]; point[0].left=0; point[0].right=0; point[0].count=1; hash[0]=0; t=0; for(int i=2; i<=n; i++) { if(a[i]==a[i-1]) { point[t].count++; point[t].right=i; } else { point[++t].left=i; point[t].right=i; point[t].num=a[i]; point[t].count=1; } hash[i]=t; } } void st(int n) { int i, j, k, m; k = (int) (log((double)n) / log(2.0)); for(i = 0; i < n; i++) { f1[i][0] = point[i].count; //递推的初值 } for(j = 1; j <= k; j++) { //自底向上递推 for(i = 0; i + (1 << j) - 1 < n; i++) { m = i + (1 << (j - 1)); //求出中间的那个值 f1[i][j] = mmax(f1[i][j-1], f1[m][j-1]); } } } //查询i和j之间的最值,注意i是从0开始的 int rmq(int i, int j) { int k = (int)(log(double(j-i+1)) / log(2.0)), t1; //用对2去对数的方法求出k return t1 = mmax(f1[i][k], f1[j - (1<<k) + 1][k]); } int solve(int a,int b) { if(hash[a]==hash[b]) return b-a+1; else if(hash[a]+1==hash[b]) { int l=point[hash[a]].right-a+1; int r=b-point[hash[b]].left+1; return mmax(l,r); } else { int l=point[hash[a]].right-a+1; int r=b-point[hash[b]].left+1; l=mmax(l,r); r=rmq(hash[a]+1,hash[b]-1); l=mmax(l,r); return l; } } int main() { int q; while(scanf("%d",&n)!=EOF) { if(n==0) break; scanf("%d",&q); for(int i=0; i<n; ++i) scanf("%d",&a[i]); init(); st(t); while(q--) { int a,b; scanf("%d%d",&a,&b);//在原序列中的区间，判断再转化为线段树上的区间 printf("%d/n",solve(a-1,b-1)); } } return 0; }
