题解：P13984 数列分块入门 9

· · 题解

题解：P13984 数列分块入门 9

题意

静态区间求众数。

因为我是莫队渣渣，所以选择用在线算法，自然联想到 P4168 [Violet] 蒲公英。

solution

首先这种东西不是线段树、树状数组等做法能做的，很容易想到分块。

离散化，分块，都是最基础的，不多说。

先想整块的处理，只需要预处理 f_{i,j} 即从第 i 块开头到第 j 块结尾的众数。

再考虑散块的处理，暴力扫散块元素时，我们要知道当前元素在整块、散块中的出现次数，我们在预处理 f 数组时顺便维护一个 cnt_{i,x} 表示从第 i 块开头到序列结尾，元素 x 的出现次数，做后缀和即可。

还有一些细节实现问题，比如每次处理散块时，要用桶维护某个元素的出现次数，每次暴力清空太慢了，我们可以把这些元素存起来，统一处理，统一清空。

块长取 \sqrt{n} 即可，时间复杂度 O(n^{1.5})，空间复杂度 O(n^{1.5})，瓶颈在 cnt 数组。

看注释吧。

code

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 5, maxb = 550;
int n, m, q, B, L, R, top, st[maxn];
//这个代码用手写栈存储散块元素以清空 
int pos[maxn], l[maxn], a[maxn], lsh[maxn];
/*
pos[i] 数组第 i 位所位于的块
l[i] 第 i 块的起始位置
a[i] 原数组
lsh[i] 离散化数组
*/ 
int buc[maxn], cnt[maxb][maxn], f[maxb][maxb];
/*
buc 处理散块时的桶
cnt[i][x] 原数组 [l[i], n] 中元素 x 的出现次数
f[i][j] 第 i 块开头到第 j 块结尾的众数 
*/
inline int find(int x) {
    //离散化 
    return lower_bound(lsh + 1, lsh + m + 1, x) - lsh;
}
inline bool cmp(int p1, int cnt1, int p2, int cnt2) {
    //比较函数，出现次数最多且最小的数即为答案 
    if (cnt1 != cnt2) return cnt1 > cnt2;
    return p1 < p2;
}
inline int get(int i, int j, int x) {
    //后缀和 
    return cnt[i][x] - cnt[j + 1][x];
}
void init() {
    B = sqrt(n);
    for (int i = 1; i <= n; i++) {
        lsh[i] = a[i];
        pos[i] = (i - 1) / B + 1;
        if (pos[i] != pos[i - 1]) {
            l[pos[i]] = i;
        } 
    }
    sort(lsh + 1, lsh + n + 1);
    m = unique(lsh + 1, lsh + n + 1) - lsh - 1;
    for (int i = 1; i <= n; i++) {
        a[i] = find(a[i]);
    }
    //预处理离散化和序列分块 
    for (int i = 1; i <= pos[n]; i++) {
        int p = -1, mxcnt = -1;
        for (int j = l[i]; j <= n; j++) {
            int cur = ++cnt[i][a[j]];
            if (cmp(a[j], cur, p, mxcnt)) {
                p = a[j];
                mxcnt = cur;
                //动态维护从第 i 块开头到原序列第 j 位的众数 
            }
            if (pos[j] != pos[j + 1]) {
                f[i][pos[j]] = p;
                //若 j 是一个块的结尾，那么目前的众数 p 即为 f[i][pos[j]] 的答案 
            }
        }
    }
    return;
}
int query(int L, int R, int res = -1, int mxcnt = -1) {
    if (pos[L] == pos[R]) {
        for (int i = L; i <= R; i++) {
            buc[a[i]]++;
            st[++top] = a[i];
            //用桶统计散块元素，用栈记录元素 
        }
        while (top) {
            int p = st[top--];
            if (buc[p] > 0) {//元素 p 还没有被清零，即还没有被当作答案统计过 
                if (cmp(p, buc[p], res, mxcnt))  {
                    res = p;
                    mxcnt = buc[p];
                    //维护众数 
                }
                buc[p] = 0;
                //清零 
            }
        }
    } else {
        if (pos[L] + 1 <= pos[R] - 1) {
            res = f[pos[L] + 1][pos[R] - 1];
            mxcnt = get(pos[L] + 1, pos[R] - 1, res);
            //处理整块 
        }
        for (int i = L; pos[i] == pos[L]; i++) {
            buc[a[i]]++; 
            st[++top] = a[i];
        }
        for (int i = R; pos[i] == pos[R]; i--) {
            buc[a[i]]++;
            st[++top] = a[i];
        }
        //用桶统计散块元素，用栈记录元素 
        while (top) {
            int p = st[top--];
            if (buc[p] > 0) {
                int tot = buc[p] + get(pos[L] + 1, pos[R] - 1, p);
                if (cmp(p, tot, res, mxcnt)) {
                    res = p;
                    mxcnt = tot;
                }
                buc[p] = 0;
            } //和上面同理，只是算上了 p 在整块中的出现次数 
        }
    }
    return lsh[res];
    //返回的是离散化之前的数值 
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    } //输入 
    init();
    for (int i = 1; i <= n; i++) {
        cin >> L >> R;
        cout << query(L, R) << '\n';
    } //询问 
    return 0;
}

STL 的栈效果可能没那么好，没必要快读快写，没必要把函数内的代码堆到主函数里，没必要开 long long ，代码习惯好一般来说没必要卡常的。

一开始这么写为什么卡常卡了一页啊？