题解：P13984 数列分块入门 9

· · 题解

为啥没有正常做法。

::::info[题意] 给出长度为 n 的序列，n 次询问区间内的最小众数。n\le 3\times 10^5。 ::::

以 B=\mathcal{O}(\sqrt n) 为块长分块，容易处理 f_{i,j} 表示第 i 个块到第 j 个块的众数出现次数以及最小众数。

对于一个询问，如果左右端点同块就暴力做掉。否则可以用 f 和 g 得到整块答案。至于散块部分，相当于往现有区间中插入 \mathcal{O}(\sqrt n) 个数。注意到插入一个数后众数出现次数至多加 1，因此考虑暴力往后 check \mathcal{O}(\sqrt n) 个出现次数。用 basic_string 存储每种颜色出现位置，记录一下每个位置是这个颜色第几次出现，则可以知道从它开始往前、往后若干个位置在哪里。判断对应位置是否在区间内即可。每插入一个数就不断 check 当前出现次数 +1 直至不合法。如果 check 结束后的出现次数大于当前出现次数，则更新答案。否则先 check 原来出现次数对于新插入的数是否合法，再和原来的众数比较大小。

时间复杂度 \mathcal{O}(n\sqrt n)，空间复杂度 \mathcal{O}(n)。

鉴于这是模板题，所以放一个代码。建议 3s 64MB。

::::success[AC Code]

#include <bits/stdc++.h>
using namespace std; const int N = 300005, K = 705; basic_string<int> p[N];
int n, a[N], B, be[N], b[N], m, id[N], bl[K], br[K], f[K][K], c[N], g[K][K];
int Q(int l, int r) {
    int u = 0, v;
    if (be[l] == be[r]) {
        for (int i = l; i <= r; ++i) {
            ++c[a[i]];
            if (c[a[i]] > u || c[a[i]] == u && a[i] < v) u = c[a[i]], v = a[i];
        }
        for (int i = l; i <= r; ++i) c[a[i]] = 0; return v;
    }
    if (be[l] + 1 < be[r])
        u = f[be[l] + 1][be[r] - 1], v = g[be[l] + 1][be[r] - 1];
    for (int i = br[be[l]], t; i >= l; --i) {
        auto chk = [&](int o) {
            return id[i] + o < p[a[i]].size() && p[a[i]][id[i] + o - 1] <= r;
        };
        t = u; while (chk(t + 1)) ++t;
        if (t > u) v = a[i];
        else if (chk(u) && a[i] < v) v = a[i];
        u = t;
    }
    for (int i = bl[be[r]], t; i <= r; ++i) {
        auto chk = [&](int o) {
            return id[i] + 1 >= o && p[a[i]][id[i] - o + 1] >= l;
        };
        t = u; while (chk(t + 1)) ++t;
        if (t > u) v = a[i];
        else if (chk(u) && a[i] < v) v = a[i];
        u = t;
    }
    return v;
}
int main() {
    scanf("%d", &n); B = sqrt(n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]), be[i] = (i - 1) / B + 1, b[i] = a[i];
    stable_sort(b + 1, b + n + 1); m = unique(b + 1, b + n + 1) - b - 1;
    for (int i = 1; i <= m; ++i) p[i] += 0;
    for (int i = 1; i <= n; ++i)
        a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b,
        id[i] = p[a[i]].size(), p[a[i]] += i;
    for (int i = 1; i <= m; ++i) p[i] += n + 1;
    for (int i = 1; i <= be[n]; ++i)
        bl[i] = br[i - 1] + 1, br[i] = min(n, i * B);
    for (int i = 1; i <= be[n]; ++i) {
        for (int j = bl[i], k = i, u = 0, v; j <= n; ++j) {
            ++c[a[j]];
            if (c[a[j]] > u || c[a[j]] == u && a[j] < v) u = c[a[j]], v = a[j];
            if (j == br[k]) f[i][k] = u, g[i][k] = v, ++k;
        }
        memset(c, 0, sizeof c);
    }
    for (int i = 1, l, r; i <= n; ++i)
        scanf("%d%d", &l, &r), printf("%d\n", b[Q(l, r)]);
    return 0;
}

::::