传送门
描述
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 102 31 105 100
- 输出143
思路
- 题意:给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<