bug已解决

1. read() 中加入 if (c == '-') f = -1;
2. 枚举左边界会超时，使用二分

#include <bits/stdc++.h>
#include <cstdio>
using namespace std;
const int N = 100010;
int n, q, l, r;
int f[N], a[N];
struct E {
    int l, r;
    int pre;
} tree[N << 2];
int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (!isdigit(c)) {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    return x * f;
}
void write(int x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
void build(int k, int l, int r) {
    tree[k].l = l;
    tree[k].r = r;
    if (l == r) {
        tree[k].pre = f[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(k << 1, l, mid);
    build(k << 1 | 1, mid + 1, r);
    tree[k].pre = max(tree[k << 1].pre, tree[k << 1 | 1].pre);
}
int ask(int k, int l, int r) {
    if (l <= tree[k].l && r >= tree[k].r)
        return tree[k].pre;
    int mid = (tree[k].l + tree[k].r) >> 1, t = 0;
    if (l <= mid)
        t = max(t, ask(k << 1, l, r));
    if (r > mid)
        t = max(t, ask(k << 1 | 1, l, r));
    return t;
}
int main() {
    while (1 + 1 == 2) {
        n = read();
        if (n == 0) return 0;
        q = read();
        f[1] = 1;
        for (int i = 1; i <= n; i++) {
            a[i] = read();
            if (i > 1) f[i] = (a[i] == a[i - 1]) ? f[i - 1] + 1 : 1;
        }
        build(1, 1, n);
        while (q--) {
            scanf("%d %d", &l, &r);
            int now = l;
            // while (now <= r && a[now] == a[now - 1]) now++;
            now = upper_bound(a + l, a + r + 1, a[l]) - a;
            int ans = max(now - l, ask(1, now, r));
            write(ans);
            putchar('\n');
        }
    }
    return 0;
}

思路

由于元素升序，那就是说相同元素必然相邻。

定义 $f_i$ 表示第 $i$ 个数据前与 $a_i$ 相等是元素数量，如下样例。

--i  :  1  2 3 4 5 6 7  8  9 10
a[i] : -1 -1 1 1 1 1 3 10 10 10
f[i] :  1  2 1 2 3 4 1  1  2 3

如果要求 $[2,9]$ 的最频繁值，也就是 $1$，出现次数为 $4$。

如果要求 $[5,10]$ 的最频繁值，也就是 $10$，出现次数为 $3$。

那么问题转化为在一个连续区间 $[l,r]$ 中查询最大值的问题，使用一个支持区间操作的数据结构即可，如ST表，线段树。

但是对于 $l$ 不一定是起始位置，比如上述 $[5,10]$ 的答案，所以需要另外确定 $l$，方案如下。

1. 暴力枚举，当全部数据相同，可能被卡成 $O(n)$；
2. 因为数据是升序的，可以二分，复杂度 $O(log_n)$

ST表

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10, INF = 0x3f3f3f3f, MOD = 1E9 + 7;
int n, q, a[N];
int F[N][22];

void ST() {
    F[1][0] = 1;
    for (int i = 2; i <= n; i++)
        F[i][0] = a[i] == a[i - 1] ? F[i - 1][0] + 1 : 1;
    for (int j = 1; j < 22; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            F[i][j] = max(F[i][j - 1], F[i + (1 << (j - 1))][j - 1]);
}

int query(int l, int r) {
    if (l > r) return 0;
    int k = log2(r - l + 1);
    return max(F[l][k], F[r - (1 << k) + 1][k]);
}

void TLE_30(int l, int r) {
    int mx = 0;
    vector<int> st(N << 1, 0);
    for (int i = l; i <= r; i++) mx = max(mx, ++st[a[i] + N]);
    cout << mx << endl;
}
void TLE_60(int l, int r) {
    int t = l;
    while (t <= r && a[t] == a[t - 1]) t++;  // 可能出现 n个相同元素，会T
    cout << max(t - l, query(t, r)) << endl;
}
void AC(int l, int r) {
    int t = upper_bound(a + l, a + 1 + r, a[l]) - a;
    cout << max(t - l, query(t, r)) << endl;
}
int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int l, r;
    while (cin >> n) {
        if (n == 0) break;
        cin >> q;
        for (int i = 1; i <= n; i++) cin >> a[i];
        ST();
        while (q--) {
            cin >> l >> r;
            TLE_30(l,r);
            TLE_60(l,r);
            AC(l, r);
        }
    }
    return 0;
}

线段树

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 1E9 + 7;
int n, q, a[N];
int f[N], d[N << 2];

void build(int s, int t, int p) {
    if (s == t) {
        d[p] = f[s]; return;
    }
    int m = s + t >> 1;
    build(s, m, p << 1), build(m + 1, t, p << 1 | 1);
    d[p] = max(d[p << 1], d[p << 1 | 1]);
}

int get(int l, int r, int s, int t, int p) {
    if (l <= s && t <= r) return d[p];
    int m = s + t >> 1, ans = 0;
    if (l <= m) ans = max(ans, get(l, r, s, m, p << 1));
    if (r > m) ans = max(ans, get(l, r, m + 1, t, p << 1 | 1));
    return ans;
}
int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int l, r;
    while (cin >> n) {
        if (n == 0) break;
        cin >> q;
        for (int i = 1; i <= n; i++) cin >> a[i];
        f[1] = 1;
        for (int i = 2; i <= n; i++)
            f[i] = a[i] == a[i - 1] ? f[i - 1] + 1 : 1;

        build(1, n, 1);
        while (q--) {
            cin >> l >> r;
            int t = upper_bound(a + l, a + r + 1, a[l]) - a;
            cout << max(t - l, get(t, r, 1, n, 1)) << endl;
        }
    }
    return 0;
}