专栏文章

题解：P13984 数列分块入门 9

ssswyhprays
P13984题解参与者 3已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@minv374w
此快照首次捕获于
2025/12/02 08:50
3 个月前
此快照最后确认于
2025/12/02 08:50
3 个月前
查看原文

分块学习笔记 / 题解：P13984 数列分块入门 9

2025/10/10 UPD - 修改了 hack 数据，现已保证 l≤rl \le r，感谢 @DimStar 喵。
2025/10/16 UPD - 修改了 hack 数据，现输入数据符合题目要求，感谢 @Asahina_Mafuyu 喵。
2025/10/19 UPD - 发现 10/16 的修改由于神秘原因没更新，再交一遍。现输入数据符合题目要求，感谢 @yhlj24444 喵。

写在题解前

调了三天，细节很多。但是深刻认识到数据结构题调代码越痛苦，印象越深刻。
文末附对拍、调试语句，hack 数据。希望能帮到各位，请多指教！

关于分块

优雅的暴力。用于解决区间操作、维护区间信息得答案的问题。
基本思想是通过划分原数据并进行一定的预处理，取得比暴力算法更优的时间复杂度。对于整块的修改和询问统筹处理，有些题可以使用线段树中的懒惰标记思想防止修改操作耗费大量时间；对于其余数据（一般是散块或询问的头尾）的修改和询问直接暴力解决。

关于离散化

一种数据处理的技巧。本题要求区间众数，需要桶来维护数字出现的次数，而 −231≤ai≤231−1-2 ^ {31} \le a_i \le 2 ^ {31} - 1，简单地把 aia_i 的值当做桶的下标会导致越界，就需要离散化。
OI-Wiki 中这样定义离散化：
离散化是一种数据处理的技巧，本质上可以看成是一种 哈希，其保证数据在哈希以后仍然保持原来的全/偏序关系。
通俗地讲就是当有些数据因为本身很大或者类型不支持，自身无法作为数组的下标来方便地处理，而影响最终结果的只有元素之间的相对大小关系时，我们可以将原来的数据按照排名来处理问题，即离散化。
在本题中，由于 aia_i 的具体数值不影响众数的计算，就可以【将原来的数据按照排名来处理问题】，简而言之，用 aia_i 的排名来代表具体数值方便桶统计，输出时再找这个排名对应的是原序列中的哪个数字即可。

题解：数列分块入门 9

强制在线版：P4168 [Violet] 蒲公英。
参考：P4168 @lcjqwq 的题解。

思路

暴力预处理两个数组 p,sp, s。其中 pijp _ i ^ j 表示第 ii 到第 jj 块最小的众数；sijs _ i ^ j 表示前 ii 块中 jj 出现了几次，那么对于一个数 kk，其在 ii 到 jj 块中出现的次数就为 sjk−si−1ks _ j ^ k - s _ {i - 1} ^ k。
对于一次询问，其解一定属于【中间整块（令左端点整块编号为 qlql，右端点整块编号为 qrqr）部分的众数】和【前后散块部分的数】的并集。而由于我们预处理了 p,sp, s，可以 O(1)O(1) 得整块部分的众数 tt，tt 在整块部分出现的次数为 sqrt−sql−1ts _ {qr} ^ t - s _ {ql - 1} ^ t，然后 O(n)O(\sqrt{n}) 扫前后散块，暴力统计散块部分中各数出现的次数，记为 ll，则对于非 tt 的数 t′t'，其出现的次数加上其在整块中出现的次数为 l+sqrt′−sql−1t′l + s _ {qr} ^ {t'} - s _ {ql - 1} ^ {t'}。

一些坑点

  • 扫散块统计前要先遍历一次散块中的所有元素，清空桶；
  • 由于是最小众数，每次询问开始时令众数为离散化后的最大值 nn，清空 nn 的桶；
  • 注意两数出现次数相等时较小者应被更新为答案，即答案更新条件应为 bucket[ii] > bucket[md] || (bucket[ii] == bucket[md] && ii < md)；
  • 看清当前要带入的是什么量，我好几次把 belong[i] 写成 i。

附件

AC Code

p13984.cppCPP
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 3e5 + 5;
const int MAXB = 6e2 + 5;

int n, tot;
int ql, qr;
int a[MAXN], t[MAXN], o[MAXN];
int belong[MAXN], bl[MAXB], br[MAXB];
int p[MAXB][MAXB]; // p_i, j: 第 i 块到第 j 块最小的众数
int s[MAXB][MAXN]; // s_i, j: 在前 i 个块内 j 出现了几次
int bucket[MAXN], md;

void Build()
{
    int sz = sqrt(n);
    tot = n / sz;
    if (n % sz) tot++;
	for (int i = 1; i <= n; i++) belong[i] = (i - 1) / sz + 1;
	for (int i = 1; i <= tot; i++) {
		bl[i] = (i - 1) * sz + 1;
		br[i] = min(i * sz, n);
	}
}

void Init()
{
    for (int i = 1; i <= tot; i++)
    {
        for (int j = bl[i]; j <= br[i]; j++)
        {
            for (int k = i; k <= tot; k++)
            {
                s[k][a[j]]++;
            }
        }
    }
    /*
    cout << "s: " << '\n';
    for (int i = 1; i <= tot; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cout << s[i][j] << ' ';
        }
        cout << '\n';
    }
    */
    for (int i = 1; i <= tot; i++)
    {
        md = n;
        bucket[md] = 0;
        for (int j = bl[i]; j <= n; j++)
        {
            int ii = a[j];
            bucket[ii] = 0;
        }
        for (int j = bl[i]; j <= n; j++)
        {
            int ii = a[j];
            bucket[ii]++;
            if (bucket[ii] > bucket[md] || (bucket[ii] == bucket[md] && ii < md))
            {
                md = ii;
            }
            p[i][belong[j]] = md;
        }
    }
    /*
    cout << "p: " << '\n';
    for (int i = 1; i <= tot; i++)
    {
        for (int j = 1; j <= tot; j++)
        {
            cout << p[i][j]<< ' ';
        }
        cout << '\n';
    }
    */
}

int Query(int ql, int qr)
{
    md = n;
    bucket[n] = 0;
    if (belong[qr] - belong[ql] <= 1)
    {
        for (int i = ql; i <= qr; i++)
        {
            int ii = a[i];
            md = ii;
            bucket[ii] = 0;
        }
        for (int i = ql; i <= qr; i++)
        {
            int ii = a[i];
            bucket[ii]++;
            if (bucket[ii] > bucket[md] || (bucket[ii] == bucket[md] && ii < md)) md = ii;
        }
    }
    else
    {
        int qll = belong[ql] + 1;
        int qrr = belong[qr] - 1;
        md = p[qll][qrr];
        int ini = md;
        bucket[md] = s[qrr][md] - s[qll - 1][md];
        // cout << "md = " << o[md] << '\n';
        for (int i = ql; i <= br[qll - 1]; i++)
        {
            int ii = a[i];
            if (ii == md) bucket[md]++;
            else bucket[ii] = s[qrr][ii] - s[qll - 1][ii];
        }
        for (int i = bl[qrr + 1]; i <= qr; i++)
        {
            int ii = a[i];
            if (ii == md) bucket[md]++;
            else bucket[ii] = s[qrr][ii] - s[qll - 1][ii];
        }
        // cout << "qll = " << qll << ", qrr = " << qrr << ", init bucket_md as " << bucket[md] << '\n';
        for (int i = ql; i <= br[qll - 1]; i++)
        {
            int ii = a[i];
            if (ii != ini)
            {
                bucket[ii]++;
                if (bucket[ii] > bucket[md] || (bucket[ii] == bucket[md] && ii < md))
                {
                    // cout << "update md as " << ii << ", bucket[ii] = " << bucket[ii] << '\n';
                    md = ii;
                }
            }
        }
        for (int i = bl[qrr + 1]; i <= qr; i++)
        {
            int ii = a[i];
            if (ii != ini)
            {
                bucket[ii]++;
                if (bucket[ii] > bucket[md] || (bucket[ii] == bucket[md] && ii < md))
                {
                    // cout << "update md as " << ii << ", bucket[ii] = " << bucket[ii] << '\n';
                    md = ii;
                }
            }
        }
    }
    return md;
}

int main()
{
    // freopen("data.in", "r", stdin);
    // freopen("sol.out" ,"w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        t[i] = a[i];
    }
    sort(t + 1, t + n + 1);
    int ulen = unique(t + 1, t + n + 1) - (t + 1);
    for (int i = 1; i <= n; i++)
    {
        int disc = lower_bound(t + 1, t + ulen + 1, a[i]) - t;
        o[disc] = a[i];
        a[i] = disc;
    }

    Build();
    Init();

    /*
    cout << "Array a after disc: ";
    for (int i = 1; i <= n; i++)
    {
        cout << a[i] << ' ';
    }
    cout << '\n';
    */

    for (int i = 1; i <= n; i++)
    {
        cin >> ql >> qr;
        cout << o[Query(ql, qr)] << '\n';
    }

    return 0;
}

对拍

P13984_main.cppCPP
#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    while (1)
    {
        system("P13984_data.exe");
        system("P13984_bf.exe");
        system("p13984.exe");
        if (system("fc sol.out bf.out")) break;
    }
    return 0;
}
P13984_data.cppCPP
#include <bits/stdc++.h>
using namespace std;

const int n = 50;
const int m = 50;
const int MOD = 19260817 / 10000;

int sf[n + 5];
int a[n + 5];

int main()
{
    freopen("data.in", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    srand(time(NULL));
    srand(rand() + 19260817);

    cout << n << '\n';
    for (int i = 1; i <= 10; i++)
    {
        while (sf[i] == 0) sf[i] = rand() % MOD - 19260817 / 10000 / 2;
    }
    a[1] = sf[rand() % 10 + 1];
    cout << a[1] << ' ';
    for (int i = 2; i <= n; i++)
    {
        cout << sf[rand() % 10 + 1] << ' ';
    }
    cout << '\n';

    for (int i = 1; i <= m; i++)
    {
        int l = rand() % n + 1;
        int r = rand() % (n - l + 1) - 1 + l;
        cout << l << ' ' << r << '\n';
    }
    return 0;
}
P13984_bf.cppCPP
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e3 + 5;

int n;
int a[MAXN], t[MAXN], o[MAXN];
int bucket[MAXN];

int main()
{
    freopen("data.in", "r", stdin);
    freopen("bf.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        t[i] = a[i];
    }
    sort(t + 1, t + n + 1);
    int ulen = unique(t + 1, t + n + 1) - (t + 1);
    for (int i = 1; i <= n; i++)
    {
        int disc = lower_bound(t + 1, t + ulen + 1, a[i]) - t;
        o[disc] = a[i];
        a[i] = disc;
    }
    for (int i = 1; i <= n; i++)
    {
        int md = n + 1;
        memset(bucket, 0, sizeof bucket);
        int l, r;
        cin >> l >> r;
        for (int j = l; j <= r; j++)
        {
            int ii = a[j];
            bucket[ii]++;
            if (bucket[ii] > bucket[md] || (bucket[ii] == bucket[md] && ii < md)) md = ii;
        }
        cout << o[md] << '\n';
    }



    return 0;
}

hack 数据

hack.inCPP
50
-938 296 502 979 -705 -958 160 -958 979 160 160 -938 -938 -705 347 -938 -613 -938 160 502 -705 160 347 -705 -613 502 161 979 979 296 161 160 -938 161 161 -958 -705 -958 296 -938 979 -938 160 161 296 347 502 -958 979 160 
43 44
27 33
32 42
25 25
48 48
8 19
13 18
20 31
13 27
11 40
25 40
22 45
27 40
20 31
23 27
42 46
1 1
29 36
27 29
11 43
12 34
27 39
1 1
18 45
5 32
15 47
1 1
31 32
24 30
30 49
43 44
47 49
42 45
41 45
45 46
35 38
43 47
19 46
35 38
3 49
15 42
10 48
7 12
49 49
48 48
43 49
36 43
10 24
19 36
2 16
hack.outCPP
160
161
-938
-613
-958
-938
-938
-705
-938
-938
161
161
161
-705
-705
-938
-938
161
979
-938
-938
161
-938
161
160
-938
-938
160
979
161
160
-958
-938
-938
296
-958
160
161
-958
-938
-938
-938
160
979
-958
-958
-958
-938
161
-938

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...