poj3368:http://poj.org/problem?id=3368
题意：给你一个非下降的序列，然后查询[l,r]内出现最多数字的次数。
题解：首先，因为序列是非下降的，所以相同的数字出现在在一起。所以，可以定义一个数组a[i]=k,表示第i个数出现的次数，另外还要记录几个东西,ll[i],rr[i],分别表示第i个数首次出现的位置和最后出现的位置。sum[i]到第i数出现结束之后一共有多少个数。准备好了这些东西之后。既可以开始了。第一步以数的个数(相同的算一个)建立线段树，叶子节点的值就是这个数出现的次数，然后维护区间最大值。2对于一个查询来说，是查询第几个数到第几个数之间出现的最大值的话，问题就爱很简单了。所以，我们要把查询转化成这样的就行了。query(l,r),我们可以通过lower_bound(sum+1,sum+temp+1)-sum,来找到l，r出现在第几个数中，然后我们查询l后面和r前面的数就可以啦 啊。对于l前面的部分，肯定是连续的，所以可以直接ll[l+1]-u得到左边的，v-rr[ed-1]得到右边的，然后3部分去最大值就可以啦。当然还有几个情况，就是1:l,r出现在同一个数中,那么可以直接u-v+1,如果是相隔一个数的话,max(sum[l]-u+1,v-sum[ed-1])即可。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+;
int ll[N],rr[N],sum[N];
int maxn[N*];
int a[N];
int n,q,temp;
void input(){
int t,tp;
scanf("%d",&t);
a[temp]=;
ll[temp]=;
for(int i=;i<=n;i++){
scanf("%d",&tp);
if(tp==t)a[temp]++;
else{
a[++temp]=;
ll[temp]=i;
rr[temp-]=i-;
t=tp;
}
}
rr[temp]=n;
}
void build(int l,int r,int rt){
if(l==r){
maxn[rt]=a[l];
return;
}
int mid=(l+r)/;
build(l,mid,rt<<);
build(mid+,r,rt<<|);
maxn[rt]=max(maxn[rt<<],maxn[rt<<|]);
}
int query(int l,int r,int rt,int from,int to){
if(l==from&&r==to){
return maxn[rt];
}
int mid=(l+r)/;
if(mid>=to)return query(l,mid,rt<<,from,to);
else if(mid<from)return query(mid+,r,rt<<|,from,to);
else{
return max(query(l,mid,rt<<,from,mid),query(mid+,r,rt<<|,mid+,to));
}
}
int u,v;
int main(){
while(~scanf("%d",&n)){
if(n==)break;
scanf("%d",&q);
temp=;
input();
memset(maxn,,sizeof(maxn));
build(,temp,);
sum[]=;
for(int i=;i<=temp;i++){
sum[i]=sum[i-]+a[i];
}
for(int i=;i<=q;i++){
scanf("%d%d",&u,&v);
int st=lower_bound(sum+,sum+temp+,u)-sum;
int ed=lower_bound(sum+,sum+temp+,v)-sum;
st++;ed--;
if(ed>=st){
int ans1=query(,temp,,st,ed);
int ans2=ll[st]-u;
int ans3=v-rr[ed];
printf("%d\n",max(ans1,max(ans2,ans3)));
}
else if(st==ed+){
printf("%d\n",v-u+);
}
else{
st--,ed++;
printf("%d\n",max(sum[st]-u+,v-sum[ed-]));
}
} }
}