Description
给你一个含有n个整数的非递减序列a1 , a2 , ... , an，要求你回答一系列的询问，如i和j (1 ≤ i ≤ j ≤ n)，回答出ai , ... , aj之间出现频率最多数字为多少次？
Input
第1行包含两个整数n和q(1 ≤ n, q ≤ 100000)
第2行为n个用空格分开的整数a1 , ... , an(-100000 ≤ ai ≤ 100000, for each i ∈ {1, ..., n})
接下来的q行，每行包含两个整数i和j。
Output
对于每一个询问输出一行，为在此区间内出现频率最多数字为多少次？
思路：
用ST表，然后类似分块的思想，分成很多块，然后直接做就行了。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
int n,m;
int w[N];
int a[N];
int fmx[N][20];
void init(){
for (int j = 0; j < 20; j ++ ){
for (int i = 1; i + (1 << j) - 1<= n; i ++ ){
if (!j){
fmx[i][j] = w[i];
}
else{
fmx[i][j] = max(fmx[i][j - 1],fmx[i + (1 << j - 1)][j - 1]);
}
}
}
}
int query(int l,int r){
if (l > r){
return 0;
}
int len = r - l + 1;
int k = log2(len);
return max(fmx[l][k],fmx[r - (1 << k) + 1][k]);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int q;
cin >> n >> q;
for (int i = 1; i <= n; i ++ ){
cin >> a[i];
if (i == 1){
w[i] = 1;
continue;
}
if (a[i] == a[i - 1]){
w[i] = w[i - 1] + 1;
}
else{
w[i] = 1;
}
}
init();
while (q -- ){
int l,r;
cin >> l >> r;
int t = l;
while (t <= r && a[t] == a[t - 1]){
t ++ ;
}
int x = query(t,r);
cout << max(t - l,x) << "\n";
}
return 0;
}