题解：P13984 数列分块入门 9

xAlec · 2025-09-12 12:38:27 · 题解

Solution

查询区间最小众数。

考虑整块和散块的关联，其实整块的最小众数预处理出来就是散块的数会影响到整块。

设块长为 T。

所以考虑预处理整块内的众数，记 num_{l,r} 表示块 l \sim r 的最小众数，直接枚举每个块右端点然后往 n 扫，这样复杂度是 O(\frac{n^2}{T})。

之后记录每个数出现的位置，因为我们需要知道每个数区间内出现次数，可以用二分解决，先找到第一个大于询问右端点的位置，再找到第一个大于等于询问左端点的位置，两者相减就是想要的出现次数。

每次查询再用散块更新答案，复杂度就是 O(T\log n)。

总复杂度 O(T\log n + \frac{n^2}{T})，在 T = \sqrt{\frac{n}{\log n}} 取得最小值 O(n\sqrt{n\log n})。

Code

#include <bits/extc++.h>
#define int long long

using namespace std;

namespace IO {
    inline int read() {
        int res = 0, f = 1;
        char ch = getchar();
        while (!isdigit(ch)) f = ch == '-' ? -1 : 1, ch = getchar();
        while (isdigit(ch)) res = (res << 1) + (res << 3) + (ch ^ 48), ch = getchar();
        return res * f;
    }
    inline void write (int x, bool flag) {
        int stk[33], top = 0;
        if (x < 0) x = -x, putchar ('-');
        do { stk[top ++] = x % 10, x /= 10; } while(x);
        while (top) putchar (stk[-- top] + '0');
        flag ? putchar ('\n') : putchar (' ');
    }
} using namespace IO;

constexpr int MAXN = 3e5 + 10;

int n, a[MAXN], val[MAXN], idx, cnt[MAXN];
vector<int> vec[MAXN];
__gnu_pbds::gp_hash_table<int,int> mp;

int blk[MAXN], sizblk, maxblk, L[MAXN], R[MAXN], ModeNum[2405][2405];

inline void initModeNum (int id) {
    int l = L[id], r = R[id], tmpPos = 0, tmpCnt = 0;
    memset (cnt, 0, sizeof (int) * (n + 5));
    for (int i = l; i <= n; i ++) {
        int pid = blk[i];
        cnt[a[i]] ++;
        if (cnt[a[i]] > tmpCnt || (cnt[a[i]] == tmpCnt && val[a[i]] < val[tmpPos]))
            tmpPos = a[i], tmpCnt = cnt[a[i]];
        ModeNum[id][pid] = tmpPos;
    }
}

inline int BinarySearch (int l, int r, int id) { return upper_bound (vec[id].begin(), vec[id].end(), r) - lower_bound (vec[id].begin(), vec[id].end(), l); }

inline int queryRange (int l, int r) {
    int lpos = blk[l], rpos = blk[r];
    int tmpCnt = ModeNum[lpos + 1][rpos - 1];
    int tmpPos = BinarySearch (l, r, tmpCnt);
    for (int i = l; i <= min (r, R[lpos]); i ++) {
        int Cnt = BinarySearch (l, r, a[i]);
        if (Cnt > tmpPos || (Cnt == tmpPos && val[a[i]] < val[tmpCnt]))
            tmpCnt = a[i], tmpPos = Cnt;
    }
    if (lpos ^ rpos) {
        for (int i = L[rpos]; i <= r; i ++) {
            int Cnt = BinarySearch (l, r, a[i]);
            if (Cnt > tmpPos || (Cnt == tmpPos && val[a[i]] < val[tmpCnt]))
                tmpCnt = a[i], tmpPos = Cnt;
        }
    }
    return tmpCnt;
}

// 预处理整块，散块更新答案

signed main() {
    n = read();
    sizblk = sqrt(n) / sqrt(__lg(n));
    for (int i = 1; i <= n; i ++) {
        a[i] = read();
        blk[i] = (i - 1) / sizblk + 1;
        if (!mp[a[i]]) {
            mp[a[i]] = ++ idx;
            val[idx] = a[i];
        }
        a[i] = mp[a[i]], vec[a[i]].push_back(i);
    }
    maxblk = blk[n];
    for (int i = 1; i <= maxblk; i ++)
        L[i] = (i - 1) * sizblk + 1, R[i] = min (i * sizblk, n);
    for (int i = 1; i <= maxblk; i ++) initModeNum(i);
    for (int i = 1; i <= n; i ++) {
        int l = read(), r = read();
        if (l > r) swap (l, r);
        write (val[queryRange (l, r)], true);
    }
    return 0;
}