题意O(-1)不用解释。。
线段树结点维护三个信息：区间内相同的数出现最多的次数maxc、区间左边第一个数出现的次数lc、区间右边第一个数出现的次数rc。
分左区间右端点和右区间左端点相同于否的情况合并区间，注意lc或rc为区间长度的情况。
//#pragma comment(linker, "/STACK:1024000000,1024000000") #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<iostream> #include<sstream> #include<cmath> #include<climits> #include<string> #include<map> #include<queue> #include<vector> #include<stack> #include<set> using namespace std; typedef long long ll; typedef pair<int,int> pii; #define pb(a) push_back(a) #define INF 0x1f1f1f1f #define lson idx<<1,l,mid #define rson idx<<1|1,mid+1,r #define PI 3.1415926535898 template<class T> T min(const T& a,const T& b,const T& c){return min(min(a,b),min(a,c));} template<class T> T max(const T& a,const T& b,const T& c){return max(max(a,b),max(a,c));} void debug() { #ifdef ONLINE_JUDGE #else freopen("d:\in.txt","r",stdin); freopen("d:\out1.txt","w",stdout); #endif } char getch() { char ch; while((ch=getchar())!=EOF) { if(ch!=' '&&ch!=' ')return ch; } return EOF; } const int maxn=100100; struct node { int lc,rc,maxc; node (int a,int b,int c):lc(a),rc(b),maxc(c){} node(){} }tree[maxn<<2]; int da[maxn]; int PushUp(node &q,node &q1,node &q2,int l,int r) { int mid=(r+l)>>1; if(da[mid]!=da[mid+1]) { q.maxc=max(q1.maxc,q2.maxc); q.lc=q1.lc; q.rc=q2.rc; }else { q.maxc=max(q1.maxc,q2.maxc,q1.rc+q2.lc); q.lc=q1.lc==mid-l+1?q1.lc+q2.lc:q1.lc; q.rc=q2.rc==r-mid?q2.rc+q1.rc:q2.rc; } return 0; } int build(int idx,int l,int r) { if(l==r) { tree[idx]=node(1,1,1); return 0; } int mid=(r+l)>>1; build(lson); build(rson); PushUp(tree[idx],tree[idx<<1],tree[idx<<1|1],l,r); return 0; } node quary(int idx,int l,int r,int tl,int tr) { if(tl<=l&&tr>=r) return tree[idx]; int mid=(r+l)>>1; node q1,q2; node q; if(mid>=tl&&mid<tr) { q1=quary(lson,tl,tr); q2=quary(rson,tl,tr); PushUp(q,q1,q2,l,r); } else { if(tl<=mid)q=quary(lson,tl,tr); if(tr>mid)q=quary(rson,tl,tr); } return q; } int main() { int n,q; while(scanf("%d",&n)!=EOF&&n) { scanf("%d",&q); for(int i=1;i<=n;i++) scanf("%d",&da[i]); da[0]=INT_MIN;da[n+1]=INT_MAX; build(1,1,n); for(int i=1;i<=q;i++) { int a,b; scanf("%d%d",&a,&b); node x=quary(1,1,n,a,b); printf("%d ",x.maxc); } } return 0; }