注意到数据 $10^5$，于是不用思考性质，直接上莫队。时间复杂度 $\Theta(n\sqrt{m})$。

此题在 P3709 亦有记载（无性质）。

#include <bits/stdc++.h>
using namespace std;

struct query {
  size_t l, r, id;
};

struct mo {
  uint32_t mx;
  vector<uint32_t> num, cnt;
  mo(size_t n) : mx(0), num(n + 1), cnt(n + 1) { cnt[0] = UINT32_MAX; }
  inline void add(size_t x) {
    --cnt[num[x]];
    ++cnt[++num[x]];
    if (num[x] > mx)
      mx = num[x];
  }
  inline void erase(size_t x) {
    if (mx == num[x] && cnt[num[x]] == 1)
      --mx;
    --cnt[num[x]];
    ++cnt[--num[x]];
  }
  inline uint32_t query() { return mx; }
};

int solve() {
  size_t n, m;
  cin >> n;
  if (n == 0)
    return 0;
  cin >> m;
  size_t bs = max(n / max(sqrt(m), 1.0), 1.0);
  vector<uint32_t> arr(n);
  unordered_map<uint32_t, uint32_t> mp;
  mp.reserve(n * 1.3);
  for (size_t i = 0; i < n; ++i) {
    cin >> arr[i];
    if (!mp.count(arr[i]))
      mp[arr[i]] = mp.size();
    arr[i] = mp[arr[i]];
  }
  vector<vector<query>> queries((n - 1) / bs + 1);
  for (size_t i = 0; i < m; ++i) {
    query q;
    cin >> q.l >> q.r;
    --q.l, q.id = i;
    queries[q.l / bs].push_back(q);
  }
  auto even_cmp = [](const query &a, const query &b) { return a.r < b.r; };
  auto odd_cmp = [](const query &a, const query &b) { return a.r > b.r; };
  mo mo(n);
  uint32_t l = 0, r = 0;
  vector<uint32_t> ans(m);
  for (size_t i = 0; i < queries.size(); ++i) {
    sort(queries[i].begin(), queries[i].end(), i & 1 ? odd_cmp : even_cmp);
    for (const auto &q : queries[i]) {
      while (l > q.l)
        mo.add(arr[--l]);
      while (r < q.r)
        mo.add(arr[r++]);
      while (l < q.l)
        mo.erase(arr[l++]);
      while (r > q.r)
        mo.erase(arr[--r]);
      ans[q.id] = mo.query();
    }
  }
  for (const auto &x : ans)
    cout << x << '\n';
  return 1;
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  while (solve())
    ;
  return 0;
}

ST表

把每一段相同的数抽象成一个数，这个数的权值就是他出现的次数

code

#include <bits/stdc++.h>
using namespace std;
#define ll long long

namespace syr
{
	const ll N = 1e5+10;
	ll n, m, l, r, cnt;
	ll a[N], t[N], x[N], y[N], st[N][25];
	ll find (ll l, ll r) {
		if (r<l) return 0;
		ll k = log2(r-l+1);
		return max(st[l][k], st[r-(1<<k)+1][k]);
	}
	void work()
	{
		while (cin>>n) {
			if (!n) return;
			cin>>m;
			for (ll i=1; i<=n; i++) cin>>a[i];
			l = r = 1;
			while (r<=n) {
				cnt++;
				while (a[r]==a[l] && r<=n) {
					t[r] = cnt;
					r++;
				}
				x[cnt] = l;
				y[cnt] = r-1;
				st[cnt][0] = r-l;
				l = r;			
			}
			for (ll i=1; i<=21; i++)
				for (ll j=1; j+(1<<(i-1))<=cnt; j++)
					st[j][i] = max(st[j][i-1], st[j+(1<<(i-1))][i-1]);
			while (m--) {
				cin>>l>>r;
				if (t[l]==t[r]) {
					cout<<r-l+1<<'\n';
					continue;
				}
				ll ans=0;
				ans = max(y[t[l]]-l+1, r-x[t[r]]+1);
				ans = max(ans, find(t[l]+1, t[r]-1));
				cout<<ans<<'\n';
			}
		}
	}
} 

int main()
{
	cin.tie(0)->sync_with_stdio(0);
	syr::work();
	return 0;
}

题意

给定一个长度为n数组a

有m次询问

每次你需要输出l-r之间出现的出现次数最多的数的出现次数

做法

维护一颗线段树

每个点维护他的ans,最左的数是什么，左侧连续相同的数的长度，最右的数是什么，右侧连续相同的数的长度

然后我们就可以合并两个节点了

node merge(node L,node R) {
	node x;
	x.ans = max(max(L.ans, R.ans), L.rid == R.lid ? L.r + R.l : 0);
	x.l = (L.l == L.len && R.lid == L.lid) ? L.l + R.l : L.l;
	x.r = (R.r == R.len && L.rid == R.rid) ? R.r + L.r : R.r;
	x.lid = L.lid;
	x.rid = R.rid;
	x.len = L.len + R.len;
	return x;
}

时间复杂度O(nlogn)

code

#include <bits/stdc++.h>
using namespace std;

const long long N = 1e5 + 10;

inline long long R() {
	long long x = 0, f = 1;
	char ch = getchar();
	while(!isdigit(ch)) {
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(isdigit(ch)) {
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	return x * f;
}

inline void W(long long x) {
	if(x < 0) {
		x = -x;
		putchar('-');
	}
	if(x > 9) W(x/10);
	putchar(x%10+'0');
}

long long n, m, a[N];

struct node {
	long long ans, lid, l, rid, r, len;
} t[N<<2];

void clear(long long l,long long r,long long i) {
	if(l == r) {
		t[i] = {0,0,0,0,0,0};
		return ;
	}
	long long mid = (l + r) >> 1;
	clear(l,mid,i<<1);
	clear(mid+1,r,i<<1|1);
}

node merge(node L,node R) {
	node x;
	x.ans = max(max(L.ans, R.ans), L.rid == R.lid ? L.r + R.l : 0);
	x.l = (L.l == L.len && R.lid == L.lid) ? L.l + R.l : L.l;
	x.r = (R.r == R.len && L.rid == R.rid) ? R.r + L.r : R.r;
	x.lid = L.lid;
	x.rid = R.rid;
	x.len = L.len + R.len;
	return x;
}

void build(long long l,long long r,long long i) {
	if(l == r) {
		t[i].ans = t[i].l = t[i].r = t[i].len = 1;
		t[i].lid = t[i].rid = a[l];
		return ;
	}
	long long mid = (l + r) >> 1;
	build(l,mid,i<<1);
	build(mid+1,r,i<<1|1);
	t[i] = merge(t[i<<1],t[i<<1|1]);
}

node qry(long long L,long long R,long long l,long long r,long long i) {
	if(L <= l && r <= R) {
		return t[i];
	}
	long long mid = (l + r) >> 1;
	node ans;
	bool ll = 0, rr = 0;
	node tl, tr;
	if(mid >= L) {
		tl = qry(L,R,l,mid,i<<1);
		ll = 1;
	}
	if(mid < R) {
		tr = qry(L,R,mid+1,r,i<<1|1);
		rr = 1;
	}
	if(!ll) ans = tr;
	else if(!rr) ans = tl;
	else ans = merge(tl,tr);
	return ans;
}

long long query(long long l,long long r) {
	return qry(l,r,1,n,1).ans;
}

void read() {
	n = R();
	if(n == 0) {
		exit(0);
	}
	m = R();
	for(long long i = 1; i <= n; i++) a[i] = R();
}

void compute() {
	build(1,n,1);
	for(long long i = 1; i <= m; i++) {
		long long l = R();
		long long r = R();
		W(query(l,r));
		putchar('\n');
	}
}

void init() {

}

int main() {
//	freopen("区间众数ex.in","r",stdin);
//	freopen("区间众数ex.out","w",stdout);
	while(1) {
		read();
		init();
		compute();
		clear(1,n,1);
	}
	return 0;
}

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

时间复杂度会不会退化我不会证，但是能 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;
}

莫队

用一个sum数组存储每个次数出现了多少次，然后如果删除这一个数判断一下sum中这个数是否只有一次，那么就将最大值减一

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define N 200005
using namespace std;
bool f1;
int n,m,p,lp,rp,ret=0,maxn=-2e9;
int a[N],k[N],ans[N],ton[N],sum[N];
struct node{
	int l,r,id;
}q[N];
inline int reads(){
	char c=getchar();
	int x=0,f=1;
	while(!isdigit(c)){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	return x*f;
}
bool cmp(node a,node b){
	if(k[a.l]==k[b.l]) return a.r<b.r;
	return k[a.l]<k[b.l];
}
void add(int x){
	ton[x]++;
	sum[ton[x]-1]--,sum[ton[x]]++;
	ret=max(ret,ton[x]);
}
void del(int x){
	ton[x]--;
	if(sum[ton[x]+1]==1&&ret==ton[x]+1) ret--;
	sum[ton[x]+1]--,sum[ton[x]]++;
}
void clr(){
	maxn=-2e9;
	ret=0;
	lp=1,rp=0;
	memset(k,0,sizeof(k));
	memset(ans,0,sizeof(ans));
	memset(ton,0,sizeof(ton));
	memset(sum,0,sizeof(sum));
}
bool f2;
signed main(){
//	freopen("A.in","r",stdin);
//	freopen("A.out","w",stdout);
//	while(1){
		clr();
		n=reads();
//		if(!n) break;
		m=reads();
		for(int i=1;i<=n;i++){
			a[i]=reads();
			maxn=max(maxn,abs(a[i]));
		}
		for(int i=1;i<=n;i++) a[i]+=maxn;
		p=sqrt(n);
		if(!p) p=1;
		for(int i=1;i<=n;i++) k[i]=(i-1)/p+1;
		for(int i=1;i<=m;i++){
			q[i].l=reads(),q[i].r=reads();
			q[i].id=i;
		}
		sum[0]=n;
		sort(q+1,q+m+1,cmp);
		lp=1,rp=0;
		for(int j=1;j<=m;j++){
			int L=q[j].l,R=q[j].r;
			while(rp<R){
				rp++;
				add(a[rp]);
			}
			while(rp>R){
				del(a[rp]);
				rp--;
			}
			while(lp<L){
				del(a[lp]);
				lp++;
			}
			while(lp>L){
				lp--;
				add(a[lp]);
			}
			ans[q[j].id]=ret;
		}
		for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
//	}
	return 0;
}
/*
10 3
-2 -2 0 0 0 0 1 2 2 2
2 3
1 10
5 10
10 3
-2 -2 0 0 0 0 1 2 2 2
2 3
1 10
5 10
0

*/

注意到本题数据 $10^5$，于是不用思考性质，直接上分块。时间复杂度 $\Theta(n \sqrt n + m\sqrt n)$。

此题在 Luogu P4168 蒲公英 和 Loj 6285 数列分块入门 9 亦有记载（无性质）。

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstddef>
#include <iostream>
#include <map>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;
istream &fin = cin;
ostream &fout = cout;
using ui = unsigned int;
using uli = unsigned long long int;
using li = long long int;
int main(void) {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    size_t n, m;
    if (!(fin >> n >> m)) return 0;
    vector<ui> a(n);
    map<ui, ui> mp;

    for (ui &i : a) {
        int x;
        fin >> x;
        i = x ^ (1u << 31);
        mp.emplace(i, mp.size());
    }


    for (ui &i : a)
        i = mp.at(i);

    constexpr size_t d = 80;
    vector precount{{vector<ui>(mp.size())}};
    precount.reserve(n / d + 1);
    {
        size_t i;

        for (i = 0; i + d < n; i += d) {
            precount.emplace_back(precount.back());

            for (size_t j = i; j < i + d; ++j)
                ++precount.back()[a[j]];
        }
    }
    vector<vector<ui>> bans;
    bans.reserve(n / d + 1);
    {
        size_t i;

        for (i = 0; i + d < n; i += d) {
            bans.emplace_back();
            vector<ui> c(mp.size());
            ++c[a[i]];
            ui ans = a[i];
            size_t j;

            for (j = i + 1; j < n; ++j) {
                if (j % d == 0)
                    bans.back().emplace_back(ans);

                ++c[a[j]];

                if (c[a[j]] > c[ans] || (c[a[j]] == c[ans] && a[j] < ans))
                    ans = a[j];
            }

            bans.shrink_to_fit();
        }
    }

    while (m--) {
        size_t l, r;
        fin >> l >> r;
        --l;
        size_t bl = l / d + 1, br = (r - 1) / d;
        unordered_map<ui, ui> c;

        if (bl >= br)
            for (size_t i = l; i < r; ++i)
                ++c[a[i]];
        else {
            c.emplace(bans[bl][br - bl - 1], precount[br][bans[bl][br - bl - 1]] -
                      precount[bl][bans[bl][br - bl - 1]]);

            for (size_t i = l; i < bl * d; ++i)
                ++c.emplace(a[i], precount[br][a[i]] - precount[bl][a[i]])
                .first->second;

            for (size_t i = br * d; i < r; ++i)
                ++c.emplace(a[i], precount[br][a[i]] - precount[bl][a[i]])
                .first->second;
        }

        fout << ranges::max_element(c,
        [](pair<ui, ui> a, pair<ui, ui> b) {
            return a.second != b.second
                   ? a.second < b.second
                   : a.first > b.first;
        })
        ->second
                << '\n';
    }

    return main();
}