You are given a sequence ofnintegersa1, a2, … , anin non-decreasing order. In addition to that, you are given several queries consisting of indicesiandj(1 ≤ i ≤ j ≤ n). For each query, determine the most frequent value among the integersai, … , aj.
Input Specification
The input consists of several test cases. Each test case starts with a line containing two integersnandq(1 ≤ n, q ≤ 100000). The next line containsnintegersa1, … , an(-100000 ≤ ai≤ 100000, for eachi ∈ {1, …, n}) separated by spaces. You can assume that for eachi ∈ {1, …, n-1}: ai≤ ai+1. The followingqlines contain one query each, consisting of two integersiandj(1 ≤ i ≤ j ≤ n), which indicate the boundary indices for the query.
The last test case is followed by a line containing a single0.
Output Specification
For each query, print one line with one integer: The number of occurrences of the most frequent value within the given range.
Sample Input10 3-1 -1 1 1 1 1 3 10 10 102 31 105 100Sample Output143
A naive algorithm may not run in time!
题意：
给出一个非降序的整数数组，你的任务是对于一系列询问，，回答区间内出现最多的值的次数
思路：
因为这个数组是非降序的，所以可以把所有相等的元素组合起来用二元组表示，例如-1,1,1,2,2,2,4就可以表示为(-1,1)(1,2)(2,3)(4,1)，其中(a,b)代表有b个连续的a。
val[i]代表第i段的数值
cnt[i]代表第i段连续的长度
num[i]表示第i个位置的数在那一段
lef[i],righ[i]分别表示第i段的左右端点位置
所求的最大值就是
1.从L到L所在的段的结束处的元素个数：righ[L]-L+1
2.从R到R所在的段的开始处的元素个数：R-lef[R]+1
3.中间第num[L]+1段到第num[R]-1段的cnt的最大值(RMQ)
答案就是1,2,3中的最大值
#include <iostream>#include <stdio.h>#include <string.h>#include <stack>#include <queue>#include <map>#include <set>#include <vector>#include <math.h>#include <bitset>#include <algorithm>#include <climits>using namespace std;#define LS 2*i#define RS 2*i+1#define UP(i,x,y) for(i=x;i<=y;i++)#define DOWN(i,x,y) for(i=x;i>=y;i–)#define MEM(a,x) memset(a,x,sizeof(a))#define W(a) while(a)#define gcd(a,b) __gcd(a,b)#define LL long long#define N 100005#define MOD 1000000007#define INF 0x3f3f3f3f#define EXP 1e-8#define lowbit(x) (x&-x)int n,q;int a[N];int val[N],cnt[N],num[N],lef[N],righ[N];int d[N][50],len;void RMQ_init(){int i,j,k;for(i = 1; i<=len; i++)d[i][0] = cnt[i];for(j = 1; (1<<j)<=len+1; j++)for(i = 1; i+(1<<j)-1<=len; 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 i,j,k,l,r;while(~scanf("%d",&n),n){scanf("%d",&q);len = 1;MEM(cnt,0);scanf("%d",&a[1]);val[len] = a[1];cnt[len] = 1;num[1] = len;lef[0] = 1;for(i = 2; i<=n; i++){scanf("%d",&a[i]);if(a[i]==a[i-1]){cnt[len]++;num[i] = len;}else{righ[len] = i-1;len++;val[len] = a[i];cnt[len] = 1;num[i] = len;lef[len] = i;}}RMQ_init();while(q–){scanf("%d%d",&l,&r);if(num[l]==num[r]){printf("%d\n",r-l+1);}else{int ans=0;if(num[l]+1<=num[r]-1)ans=RMQ(num[l]+1,num[r]-1);ans = max(ans,max(righ[num[l]]-l+1,r-lef[num[r]]+1));printf("%d\n",ans);}}}return 0;}
但我自信，我能点亮心烛，化解心灵的困惑。
