最近在研究线段树这个数据结构，发现这东西还挺耐玩的，它没有固定的模式，具体的构建方法要依据不同题目的具体要求而定，虽然如此，不过大致的思路还是差不多，充其量不过改改节点里面的域罢了。
这题我看了半天，因为看到有区间了，而且数据量又很大，显然要用log L的算法，于是只能是线段树，可问题在于怎么维护这颗线段树？
由于给出的序列一定是非递减的，所以如果两个数字相同的话，它们中间的数字肯定相同。
具体的算法是这样的：
首先对给出的序列进行离散化统计，将相同的数字压缩成一个节点，然后统计出这个压缩后的节点在原序列中起点和终点的位置，以及出现的次数等。当然也要记录原数字在离散化后的序列中的位置。
之后就是查询，比方说[a,b]
1.如果a,b属于同一个组，那么区间长度就是我们想要的答案 b-a+1;
2.如果a,b组号相差1，说明该区间被中间截断了，只要分别研究两侧的区间，取大值即可Max(c-a+1,b-c) ---其中c是中间点---
3.如果a,b组号相差大于1，先取出两侧进行研究，取大值，然后再用线段树，算出中间区间的最大值，与刚才的那个数比较，取出最大值即可。
//This is the source code for POJ 3368
//Coded by abilitytao
//Time:2009年7月24日21:03:20
//PS:This is the first time to using the method of discretization and the Data Structure Segment Tree to solve Problem.
//Worth to Memorize.
//Many thanks to the people on the Internet to share their codes.
//And Special thanks to the Blog owner "英雄哪里出来".
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
using namespace std;
#define MAX 100010
struct point
{
int left;
int right;
int num;
int count;
}p[MAX];//这个数组用来存储离散化之后点的信息
int myarray[MAX];
int n,q,T;
int hash[MAX];//第i个数在新的分组中的编号
struct Segnode
{
int num;//统计那个频率最高的数字
int count;//统计频率最高的数字出现的次数
Segnode *lchild;//指向左孩子
Segnode *rchild;//指向右孩子
}Segnodeset[MAX];//预先开辟很多节点以备使用，可以提升效率
Segnode *Newnode()
{
static int countnum=0;
Segnode *temp=&Segnodeset[countnum++];
temp->lchild=NULL;
temp->rchild=NULL;
return temp;
}
void init()//离散化过程
{
T=1;
p[T].left=1;
p[T].right=1;
p[T].count=1;
p[T].num=myarray[1];
hash[1]=1;
int i;
for(i=2;i<=n;i++)
{
if(myarray[i]==myarray[i-1])
{
p[T].count++;
p[T].right=i;
}
else
{
T++;
p[T].num=myarray[i];
p[T].count=1;
p[T].left=i;
p[T].right=i;
}
hash[i]=T;
}
}
Segnode *Build (int l,int r)//建立线段树，建立的同时统计区间上的最高频率
{
Segnode *root=Newnode();
if(l==r)
{
root->count=p[l].count;
root->num=p[l].num;
return root;
}
int mid=(l+r)>>1;
root->lchild=Build(l,mid);
root->rchild=Build(mid+1,r);
if(root->lchild->count > root->rchild->count)
{
root->num=root->lchild->num;
root->count=root->lchild->count;
}
else
{
root->num=root->rchild->num;
root->count=root->rchild->count;
}
return root;
}
int Query(Segnode *root,int a,int b,int l,int r)//查询函数
{
if(a==l&&b==r)
{
return root->count;
}
int mid=(l+r)>>1;
if(b<=mid)
{
return Query(root->lchild,a,b,l,mid);
}
else if(mid+1<=a)
{
return Query (root->rchild,a,b,mid+1,r);
}
else
{
int x=Query(root->lchild,a,mid,l,mid);
int y=Query(root->rchild,mid+1,b,mid+1,r);
return x>y?x:y;
}
}
int solve(Segnode *root,int a,int b)//算法核心在这个函数
{
if(hash[a]==hash[b])
{
return b-a+1;
}//如果查询的两个数在同一组中，很显然最大的频数应该等于区间长度
else if(hash[a]+1==hash[b])
{
int l=p[hash[a]].right-a+1;
int r=b-p[hash[b]].left+1;
return l>r?l:r;
}//如果组号相差一，则中间有分段点，截断之后取大的
else
{
int l=p[hash[a]].right-a+1;
int r=b-p[hash[b]].left+1;
int MAXNUM=l>r?l:r;
int ans=Query(root,hash[a]+1,hash[b]-1,1,T);
return MAXNUM>ans?MAXNUM:ans;
}
}
inline void put(int x)//用字符串输出，用以节省OI时间 PS:不过貌似作用不大
{
if(x< 0)
{
putchar('-');
x = -x;
}
if(x == 0){
putchar('0');
return;
}
char s[20];
int bas = 0;
for(;x;x/=10)s[bas++] = x%10+'0';
for(;bas--;)putchar(s[bas]);
return;
}
int main()
{
int i;
int a,b;
Segnode *root;
while(scanf("%d",&n))
{
if(n==0)
break;
scanf("%d",&q);
for(i=1;i<=n;i++)
{
scanf("%d",&myarray[i]);
}
init();
root=Build(1,T);
while(q--)
{
scanf("%d%d",&a,&b);
put(solve(root,a,b));
putchar('\n');
}
}
return 0;
}