传送门

描述

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.

输入

he 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

思路

• 题意：给n个数和m次询问，这n个数严格递增。对每次询问，找出区间[l,r]中出现次数最多的数，输出它出现的次数。
• 先预处理，用st[i][0]记录a[i]是在相同位置中第几个出现的，如样例中，st[i][0]（i=1->n）={1,2,1,2,3,4,1,1,2,3}。
• st[i][j]记录[i,i+(1<<j)]中最大的st[x][0]。但这并不一定是[i,i+(1<<j)]中出现最多的次数
• 对于询问的每个区间[l,r]，先找到第一个比a[l]大的数，假如得出有x个a[l]，那么st[l+x,r]就一定是区间[l+x,r]中出现最多的次数。这样就得到答案为max(x,Find(l+x,r))。

  Code

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

  #include #include #include #include #include #define INIT(a,b) memset(a,b,sizeof(a)) using namespace std; const int maxn=1e5+7; int n,m,a[maxn]; int ans[maxn][30]; void Rmq(){ for(int j=1;(1< <=n;j++) for(int i=1;i+(1< <=n;i++) ans[i][j]=max(ans[i][j-1],ans[i+(1<<(j-1))][j-1]); } int Find(int l,int r){ int k=log(double(r-l+1))/log(2.0); return max(ans[l][k],ans[r-(1<