题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1806
题目大意：给你一个非降序排列的整数数组，你的任务是对于一系列的询问，（i，j），回答序列中出现次数最多的数的个数；
如下图所示：
AC代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
#include<string>
#include<cmath>
using namespace std;
const int N = 1e5+;
int a[N],b[N];
int dp[N][];
int n,m;
//构造和寻找的代码，来自大白书
void buildrmq( )
{
for(int i=;i<n;i++)
dp[i][]=b[i];
for(int j=;(<<j)<=n;j++)
for(int i=;i+(<<j)-<n;i++)
dp[i][j]=max(dp[i][j-],dp[i+(<<(j-))][j-]);
}
int search(int s,int v)
{
int k = ;
while(<<(k+) <= v-s+) k++;
return max(dp[s][k],dp[v-(<<k)+][k]);
}
int bi_search(int s,int t)
{
int tmp=a[t];
int l=s;
int r=t;
int mid;
while(l<r)
{
mid=((l+r)>>);
if(a[mid]>=tmp) r=mid;
else l=mid+;
}
return r;
}
int main()
{
int T;
while(scanf("%d",&n) && n)
{
memset(b,,sizeof(b));
memset(dp,,sizeof(dp));
scanf("%d",&m);
for(int i =; i<n; i++)
scanf("%d",&a[i]);
a[n] = a[n-]+;
for(int i =n-; i>=; i--)//倒序统计单个数在当前段出现的次数
{
if(a[i] == a[i+])
{
b[i] = b[i+]+;
}
else b[i] =;
}
buildrmq( );//构造RMQ函数
int L,R,ans;
for(int i=; i<=m; i++)
{
scanf("%d %d",&L,&R);
L = L-;R = R-;//题目中是从1开始计数的；
int temp = bi_search(L,R);//寻找数组中最左端等于a[R]的数
ans = b[temp] - b[R]+; //统计和最左边相同的数出现的次数
if(L == temp) printf("%d\n",ans);//如果这一区间中的数字相同的话，直接左边减去右边
else printf("%d\n",max(ans,search(L,temp-)));//否则，寻找（L,temp）中的最大数，进行比较
}
}
return ;
}
AC代码2：线段树
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1e5+;
int a[N];
int ans ;
struct node
{
int L,R,count,fre;
int lcount,lfre;
int rcount,rfre;
}tree[*N];
/*
l,r存该节点的边界。
count存该节点中出现最多的数字的个数，fre存该节点中出现最多的数字。
lcount 存该节点左端连续出现的数字的个数， lfre存该节点左端连续出现的数字。
rcount 存该节点右端连续出现的数字的个数， rfre存该节点右端连续出现的数字。
*/
void build(int l,int r,int v)
{
tree[v].L = l;
tree[v].R = r;
if(l == r)
{
tree[v].fre = tree[v]. rfre = tree[v].lfre = a[r];
tree[v].count = tree[v].lcount = tree[v].rcount = ;
return ;
}
int mid = (l+r)/;
build(l,mid,v*);
build(mid+,r,v*+);
int tmpc,tmpf;
if(tree[v*].count>tree[v*+].count)
{
tree[v].count = tree[v*].count;
tree[v].fre = tree[v*].fre;
}
else
{
tree[v].count = tree[v*+].count;
tree[v].fre = tree[v*+].fre;
}
tree[v].lcount = tree[v*].lcount;
tree[v].rcount = tree[v*+].rcount;
if(tree[v*].rfre == tree[v*+].lfre)
{
tmpc = tree[v*].rcount +tree[v*+].lcount;
tmpf = tree[v*].rfre;
if(tree[v].count<tmpc)
{
tree[v].count = tmpc;
tree[v].fre = tmpf;
}
if(tree[v*].lfre == tree[v*+].lfre)
tree[v].lcount = tree[v].lcount+tree[v*+].lcount;
if(tree[v*].rfre == tree[v*+].rfre)
tree[v].rcount= tree[v*].rcount+tree[v].rcount;
}
tree[v].lfre = tree[v*].lfre;
tree[v].rfre = tree[v*+].rfre;
}
void update(int x,int y,int v)
{
int mid,s1,s2;
if(tree[v].L == x && tree[v].R == y)
{
if(tree[v].count>ans)
ans = tree[v].count;
return ;
}
mid = (tree[v].L+tree[v].R)/;
if(y<=mid) update(x,y,v*);
else if(x>mid) update(x,y,v*+);
else {
update(x,mid,v*);
update(mid+,y,v*+);
if(tree[v*].rfre == tree[v*+].lfre)
{
if(a[x] != tree[v*].rfre) s1 = tree[v*].rcount;
else s1 = mid-x+;
if(a[y]!=tree[v*+].lfre) s2 = tree[v*+].lcount;
else s2 = y - mid;
if(s1+s2>ans) ans = s1+s2;
}
}
}
int main()
{
int m,n,x,y;
while(scanf("%d",&m) && m)
{
scanf("%d\n",&n);
for(int i=;i<=m;i++)
scanf("%d",&a[i]);
build(,m,);
for(int i=;i<=n; i++)
{ ans = ;
scanf("%d %d",&x,&y);
if(x==y) {printf("1\n");continue;}
update(x,y,);
printf("%d\n",ans);
}
}
return ;
}