评测状态 Unaccepted 评测分数 9 求条

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5, K = 555; 

int n, m, k, sk, ID[N], L[K], R[K], a[N], sF[K][N], t[N], re[N], mode[K][K], q, town[N];

int getSum(int l, int r, int x) {
    return (l <= r ? sF[r][x] - sF[l - 1][x] : 0);
}

void init(int n) {
    k = sqrt(n);
    for (int i = 1; i <= n; i ++ )
        ID[i] = (i - 1) / k + 1;
    sk = ID[n];
    for (int i = 1; i <= sk; i ++ )
        L[i] = (i - 1) * k + 1,
        R[i] = min(n, i * k);

    for (int i = 1; i <= n; i ++ )  t[i] = a[i];
    sort(t + 1, t + n + 1);
    m = unique(t + 1, t + n + 1) - t - 1;
    for (int i = 1, x; i <= n; i ++ )
        x = lower_bound(t + 1, t + m + 1, a[i]) - t,
        re[x] = a[i], a[i] = x;
    for (int i = 1; i <= n; i ++ ) {
        if (i != 1 && ID[i] != ID[i - 1])
            for (int j = 1; j <= m; j ++ )
                sF[ID[i]][j] = sF[ID[i - 1]][j];
        sF[ID[i]][a[i]] ++ ;
    }
    for(int i = 1; i <= sk; i ++ )
        for (int j = i; j <= sk; j ++ ) {
            int maxSum = 0;
            if (i != j) {
                mode[i][j] = mode[i][j - 1];
                maxSum = getSum(i, j - 1, mode[i][j - 1]);
            }
            for (int k = L[j]; k <= R[j]; k ++ )
                if (getSum(i, j, a[k]) > maxSum || (getSum(i, j, a[k]) == maxSum && a[k] < mode[i][j])) {
                    maxSum = getSum(i, j, a[k]);
                    mode[i][j] = a[k];
                }
        }
}

int ask(int l, int r) {
    int maxSum = 0, nowMode = -1;
    if (ID[l] == ID[r]) {
        for (int i = l; i <= r; i ++ )
            if ((++ town[a[i]]) > maxSum || (town[a[i]] == maxSum && a[i] < nowMode)) {
                maxSum = town[a[i]];
                nowMode = a[i];
            }
        for (int i = l; i <= r; i ++ ) town[a[i]] = 0;
        return re[nowMode];
    }
    nowMode = mode[ID[l] + 1][ID[r] - 1];
    maxSum = getSum(ID[l] + 1, ID[r] - 1, nowMode);
    for (int i = l; i <= R[ID[l]]; i ++ )
        if ((++ town[a[i]] + getSum(ID[l] + 1, ID[r] - 1, a[i])) > maxSum || (town[a[i]] + getSum(ID[l] + 1, ID[r] - 1, a[i]) == maxSum && a[i] < nowMode)) {
            maxSum = town[a[i]] + getSum(ID[l] + 1, ID[r] - 1, a[i]);
            nowMode = a[i];
        }
    for (int i = L[ID[r]]; i <= r; i ++ )
        if ((++ town[a[i]] + getSum(ID[l] + 1, ID[r] - 1, a[i])) > maxSum || (town[a[i]] + getSum(ID[l] + 1, ID[r] - 1, a[i]) == maxSum && a[i] < nowMode)) {
            maxSum = town[a[i]] + getSum(ID[l] + 1, ID[r] - 1, a[i]);
            nowMode = a[i];
        }
    for (int i = l; i <= R[ID[l]]; i ++ ) town[a[i]] = 0;
    for (int i = L[ID[r]]; i <= r; i ++ ) town[a[i]] = 0;
    return maxSum;
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    cin >> n >> q;
    for (int i = 1; i <= n; i ++ )  cin >> a[i];
    init(n);
    
    for (int i = 1, l, r, lastAns = 0; i <= q; i ++ ) {
        cin >> l >> r;
        if (l > r) swap(l, r);
        cout << (lastAns = ask(l, r)) << '\n';
    }
    return 0;
}