如题。我会 $O(n logn)$ 的做法。

但看官方题解上说$O(n\sqrt n)$ 也可以卡常过去，但我自己写的$O(n\sqrt n)$静态区间众数奇慢无比，而且空间巨大。请问各位是怎么写的？

这是我的$O(n\sqrt n)$静态区间众数代码：

#include<ctime>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>

#define rint register int
#define I inline
#define nx putchar('\n')

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

template<class T> inline void read(T &x){
	x=0;char c=getchar();int f=1;
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=x*10+c-'0';c=getchar();} x*=f;
}

const int N=100010,M=320;

int n,q,T,m;
int a[N],b[N],tot[M];
vector<int> pos[N];
int F[M][N],A[M][M][M],B[M][N];
int mdcnt[M][M];
int tmp[N];

#define id(x) ((x-1)/T+1)
#define L(x) ((x-1)*T+1)
#define R(x) (x*T>n?n:x*T)

I int Getcnt(int pos,int x){
	int p=id(pos);
	return F[p-1][x]+A[p][pos-R(p-1)][B[p][a[pos]]];
}

void Init_count(){
	memcpy(b,a,sizeof b);
	for(rint i=1;i<=m;i++) {
		for(rint j=1;j<=n;j++) F[i][j]=F[i-1][j];
		for(rint j=L(i);j<=R(i);j++) F[i][a[j]]++;
		sort(b+L(i),b+R(i)+1);
		for(rint j=L(i);j<=R(i);j++) 
			if(b[j]!=b[j-1]) B[i][a[j]]=++tot[i];
		for(rint j=L(i);j<=R(i);j++){
			if(j>L(i)) for(rint k=1;k<=tot[i];k++) A[i][j][k]=A[i][j-1][k];
			A[i][j][B[i][a[j]]]++;
		}	
	}
}

int Query(int l,int r){
	int p=id(l),q=id(r);
	int res=0;
	if(p==q){	
		for(rint i=l;i<=r;i++) res=max(res,Getcnt(r,a[i])-Getcnt(l-1,a[i]));
		return res;
	}
	if(p+1<q) res=max(res,mdcnt[p+1][q-1]);
	for(rint i=l;i<=R(p);i++)	res=max(res,Getcnt(r,a[i])-Getcnt(l-1,a[i]));
	for(rint i=L(q);i<=r;i++) res=max(res,Getcnt(r,a[i])-Getcnt(l-1,a[i]));
	return res;
}

int main(){
	read(n),read(q);
	for(rint i=1;i<=n;i++) read(a[i]),pos[a[i]].push_back(i);
	T=sqrt(n); m=id(n); Init_count();
	for(rint i=1;i<=m;i++){
		memset(tmp,0,sizeof tmp);
		for(rint j=i;j<=m;j++){
			if(j!=i) mdcnt[i][j]=mdcnt[i][j-1];
			for(rint k=L(j);k<=R(j);k++) {
				tmp[a[k]]++;
				if(tmp[a[k]]>mdcnt[i][j]) mdcnt[i][j]=tmp[a[k]];
			} 
		}
	}
	while(q--){
		int l,r; read(l),read(r);
		printf("%d\n",max(1,2*Query(l,r)-(r-l+1)));
	}
	return 0;
} 

如果知道相关资料丢个链接也行。 谢谢！