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.
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

题意

多组数据，每组数据第一行两个数字n,q，表示n个整数和q次询问，然后给n个数字，每次询问两个数字i,j，表示区间【i，j】中出现次数最多的值所出现的次数。

解题思路

离散化+维护区间最大值。
1.ai的范围在-100000~100000之间，其实本题直接加上100000可是可行的，担有些题目数据远远超过100000，所以还是用离散化好点。
2.肯定要记录每个点出现的左端点和右端点。

第二行是原数组，第三行是离散化后数组，第四行是左端点数组，第五行是右端点数组。
3.两个端点值可能只取了部分，即可能有些端点值在区间外，所以两个端点需要特判一下，假设区间为【q，w】，左端点的相同数字出现次数就是w-l[temp[w]]+1，右端点就是r[temp[q]]-q+1，代码如下

int ans=max(w-l[temp[w]]+1,r[temp[q]]-q+1);

因为我们已经将ai离散化处理过了，所以只需要求一下for (int i=q+1;i<=w-1;i++)数字i出现的最大值就好了，线段树查询操作logn，完毕。

4.多组输入，一定要memset，血的教训。

AC代码

#include <iostream>
#include <cstring>
#define ll long long
#define lson left,mid,k<<1
#define rson mid+1,right,k<<1|1
#define imid int mid=(left+right)>>1
using namespace std;
int a[100005],temp[100005],l[100005],r[100005];
int ql,qr;
struct node
{
	int l;
	int r;
	int maxn;
}que[200005*4];
void push_up(int k)
{
	que[k].maxn=max(que[k<<1].maxn,que[k<<1|1].maxn);
}
void build(int left,int right,int k)
{
	que[k].l=left;
	que[k].r=right;
	if (left==right)
	{
		que[k].maxn=a[left];
		return;
	}
	imid;
	build(lson);
	build(rson);
	push_up(k);
}
int query(int left,int right,int k)
{
	if (qr<left||ql>right)
	return 0;
	if (ql<=left&&right<=qr)
	return que[k].maxn;
	imid;
	return max(query(lson),query(rson));
}
int main()
{
	//freopen("123.txt","w+",stdout);
	int n,m,q,w;
	while (true)
	{
		memset(a,0,sizeof(a));
		scanf("%d",&n);
		if (n==0)
		return 0;
		scanf("%d",&m);
		int x=1,pre,t;
		scanf("%d",&pre);
		temp[1]=x;
		a[x]++;
		l[1]=1;
		for (int i=2;i<=n;i++)
		{
			scanf("%d",&t);
			if (t!=pre)
			{
				r[x]=i-1;
				x++;
				l[x]=i;
			}
			a[x]++;
			pre=t;
			temp[i]=x;
		}
		r[x]=n;
		/* for (int i=1;i<=n;i++) printf("%d%c",temp[i],i!=n?' ':'\n'); for (int i=1;i<=n;i++) printf("%d%c",l[i],i!=n?' ':'\n'); for (int i=1;i<=n;i++) printf("%d%c",r[i],i!=n?' ':'\n'); return 0; */
		build(1,x,1);
		while (m--)
		{
			scanf("%d%d",&q,&w);
			//printf("%d %d\n\n",temp[q-1],temp[w-1]);
			if (temp[q]==temp[w])
				printf("%d\n",w-q+1);
			else
			{
				ql=temp[q]+1;
				qr=temp[w]-1;
				int ans=max(w-l[temp[w]]+1,r[temp[q]]-q+1);
				if (ql<=qr)
				ans=max(ans,query(1,x,1));
				printf("%d\n",ans);
			}
		}
	}
}