分享一下我的乱搞分块做法。

时间复杂度会不会退化我不会证，但是能 A 就是正解。

看到区间查询就可以想到线段树或分块。但是对于不同部分之间如何合并不好搞，因为有可能有一串相同数跨块。

所以，为了解决跨块，我们直接在分块的时候如果碰到一个块结束了但是这一组相同数还没结束的情况，我们就让这个块继续，直到这段相同数结束我们再结束这个块。

代码（写的很丑见谅）：

#include <bits/stdc++.h>
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
using namespace std;
int read(){
	int k=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0' && c<='9'){
		k=k*10+c-'0';
		c=getchar();
	}
	return k*f;
}
void write(int x){
	if(x<0) x=-x,putchar('-');
	if(x>=0 && x<=9) putchar(x+'0');
	if(x>=10) write(x/10),putchar(x%10+'0');
}
int a[100020];
int st[100020];//记录每一块的起始位置 
int ed[300020];//记录值为j的数字的终止位置 
int blk[100020];//记录每个数属于哪个块 
int part[100020];//记录每块最大值 
const int N=1e5+500;
int tot=0;
int main(){
    int n=read();
    while(n!=0){
    	memset(blk,0,sizeof(blk));
        a[0]=N;
    	int len=sqrt(n),m=read(),nowlen=0,tot=0;
		//nowlen:当前块长 tot:总块数 
        st[++tot]=1;
        for(int i=1;i<=n;i++){
			a[i]=read();
            if(a[i]!=a[i-1]) ed[a[i-1]+N]=i-1; 
            nowlen++;
            if(nowlen>len){//如果这一块长度已超过预定长度 
                while(i+1<=n && a[i]==a[i-1]) a[++i]=read();//读完所有相同数 
                if(i>=n){
                    ed[a[i]+N]=n;
                    st[tot+1]=n+1;
                    break;
                }
                ed[a[i-1]+N]=i-1;
                st[++tot]=i;
                nowlen=1;
            }
        }
        ed[a[n]+N]=n;//别忘了最后一组 
        for(int i=1;i<=tot+1;i++){
            blk[st[i]]=i;
        }
        for(int i=n;i>=1;i--){
            if(blk[i]==0) blk[i]=blk[i+1];
		}
		
        for(int i=1;i<=tot;i++){//计算每块内众数出现次数 
            int maxtime=-1;
            for(int j=st[i];j<st[i+1];j++){
                int tim=1;
                while(a[j]==a[j-1]){
                    tim++;
                    j++;
                }
                maxtime=max(maxtime,tim);
            }
            part[i]=maxtime;
        }
        
        for(int j=1;j<=m;j++){
            int l=read(),r=read();
            if(l==r){
                write(1);puts("");
                continue;
            }
            int l2=blk[l];
            int maxlen=-1;
            int ilast=l;
            for(int i=ed[a[l]+N];i<=r && i<st[l2];i=ed[a[i]+N]){
                int noel=(i+1)-ilast;
                maxlen=max(maxlen,noel);
                i++;
                ilast=i;
            }
            int r2=blk[r]-1;
            for(int i=l2;i<r2;i++){
                maxlen=max(maxlen,part[i]);
            }
            r2=max(l,st[r2]);
            ilast=r2;
            for(int i=ed[a[r2]+N];i<=r;i=(i<=r?ed[a[i]+N]:i)){
            	
                maxlen=max(maxlen,(i+1-ilast));
                i++;
                ilast=i;
            }
			maxlen=max(maxlen,r+1-ilast);
            write(maxlen);puts("");
        }
        n=read();
    }
    return 0;
}