题目大意：给你一个含n个整数的不下降序列，现需查询某个区间内出现次数最多的数，对于每次查询输出出现最多的次数即可。
分析：由于序列是有序的，所以一个数如果在序列中出现多次，那么一定是连续出现的，这样的话就可以把问题转化为区间染色问题，查询的是某个区间中最长的同色区间的长度。区间保存的关键信息有，区间内的某数出现的最大次数，区间最左边的数及其在该区间内出现的次数，区间最右边的数及其在该区间内出现的次数。保存左右两边的信息为为了更新父结点，因为父结点的最大answer可能由左儿子和右儿子合并得到。
这题我一开始用堆实现的线段树，发现了很多问题，用堆实现的线段树中有很多没有用到的空间，处理不好会造成结果错误。（求区间最值时可以将其初始化为正负无穷大）
思考：若给的序列不是有序的，那该如何做？
View Code
#include <stdio.h> #define MAX(a,b) ((a)>(b)?(a):(b)) #define MIN(a,b) ((a)<(b)?(a):(b)) #define N 100010 int n,q; int a[N]; int max[4*N]; int maxl[4*N]; int maxr[4*N]; int al[4*N]; int ar[4*N]; void update(int cur) { int ls=cur<<1,rs=cur<<1|1; max[cur]=MAX(max[cur],MAX(max[ls],max[rs])); if(al[rs]==ar[ls]) max[cur]=MAX(max[cur],maxl[rs]+maxr[ls]); maxl[cur]=maxl[ls]; if(al[ls]==ar[ls] && ar[ls]==al[rs]) maxl[cur]+=maxl[rs]; maxr[cur]=maxr[rs]; if(ar[rs]==al[rs] && al[rs]==ar[ls]) maxr[cur]+=maxr[ls]; al[cur]=al[ls]; ar[cur]=ar[rs]; } void build(int cur,int x,int y) { int mid=x+y>>1,ls=cur<<1,rs=cur<<1|1; if(x==y) { max[cur]=maxl[cur]=maxr[cur]=1; al[cur]=ar[cur]=a[x]; return; } build(ls,x,mid); build(rs,mid+1,y); max[cur]=0; update(cur); } int query(int cur,int x,int y,int s,int t) { int mid=(x+y)>>1,ls=cur<<1,rs=cur<<1|1; if(x>=s && y<=t) return max[cur]; int l=0,r=0,ret; if(mid>=s) l=query(ls,x,mid,s,t); if(mid+1<=t) r=query(rs,mid+1,y,s,t); if(l && r) { ret=MAX(l,r); if(ar[ls]==al[rs]) ret=MAX(ret,MIN(maxr[ls],mid-s+1)+MIN(maxl[rs],t-mid)); } else ret=l+r; return ret; } int main() { while(scanf("%d",&n),n) { scanf("%d",&q); for(int i=1;i<=n;i++) scanf("%d",&a[i]); build(1,1,n); while(q--) { int a,b; scanf("%d%d",&a,&b); printf("%d\n",query(1,1,n,a,b)); } } return 0; }