爱站程序员基地11235 – Frequent values
You are given a sequence of n integers a 1 ,a 2 ,…,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 1 ,…,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.
Note: A naive algorithm may not run in time!
Sample Input
10 3
-1 -1 1 1 1 1 3 10 10 10
2 3
1 10
5 10
0
Sample Output
1
4
3
#include<cstdio>#include<algorithm>using namespace std;#define ll long long#define lowbit(x) x&(-x)#define update addconst ll maxn=10e5+5;int value[maxn],counts[maxn],lefts[maxn],rights[maxn],num[maxn],d[maxn][32];/*做题思路：从区间左右端点削掉它们所在的区间并分别统计消掉的数的个数并判断是否在同一区间上若是则只输出r-l+1否则判断削掉后原区间是否存在如不存在输出两者的最大值，否则查询中间区间的最大值然后输出三者最大值value:储存原数组元素counts:统计每个数组元的数量（对应的新索引值）lefts:对应每一个元素（所在新索引值）的左端点rights:右端点num:每一个元素对应的新索引值*/void RMQ_init(int m){for(int i=1;i<=m;i++)d[i][0]=counts[i];for(int j=1;(1<<j)<=m;j++)for(int i=1;i+(1<<(j))-1<=m;i++)d[i][j]=max(d[i][j-1],d[i+(1<<(j-1))][j-1]);}int RMQ(int l,int r){int k=0;while((1<<(k+1))<=r-l+1)k++;return max(d[l][k],d[r-(1<<(k))+1][k]);}int main(){int n,q;while(scanf(\"%d\",&n)&&n){scanf(\"%d\",&q);for(int i=1;i<=n;i++)scanf(\"%d\",value+i);int fronts=value[1],lef=1;int m=1;int backs=value[n],rig=n;for(int i=1;i<=n;i++){if(fronts!=value[i])m++,lef=i,fronts=value[i];if(backs!=value[n-i+1])rig=n-i+1,backs=value[n-i+1];num[i]=m;lefts[i]=lef;counts[m]++;rights[n-i+1]=rig;}RMQ_init(m);for(int i=1;i<=q;i++){int l,r;scanf(\"%d%d\",&l,&r);if(num[l]==num[r]){printf(\"%d\\n\",r-l+1);}else {int llen=rights[l]-l+1;int rlen=r-lefts[r]+1;l=num[l]+1;r=num[r]-1;int mlen=0;if(l<=r)mlen=RMQ(l,r);printf(\"%d\\n\",max(mlen,max(llen,rlen)));}}for(int i=1;i<=m;i++)counts[i]=0;}}
