题解：P13984 数列分块入门 9

DrDuck · 2025-09-06 15:03:09 · 题解

回滚莫队何尝不是一种分块呢

本来想打个朴素分块结果发现被卡空间了，发现可以离线，遂使用莫队。

先对序列进行离散化。

然后发现区间众数添加容易（开一个桶就可以解决了），删除比较难（因为次大值未知），所以套一个回滚莫队就可以了。不会的可以去学习模板。

然后发现这道题不就是弱化版的历史的研究吗？

时间复杂度 O(n \sqrt n)。

CODE

#include<bits/stdc++.h>
#define int long long
#define pii pair<int, int>
using namespace std;
const int maxn = 3e+5 + 5;
int n, m, sq, tot;
pii res;
int a[maxn], b[maxn], cnt[maxn], bar[maxn], ans[maxn], bel[maxn];
struct node
{
    int l, r, id;
    friend bool operator < (const node &x, const node &y)
    {
        if (bel[x.l] != bel[y.l])
        {
            return x.l < y.l;
        }
        return x.r < y.r;
    }
}q[maxn];
void add(int x)
{
    cnt[x]++;
    res = max(res, {cnt[x], -b[x]});
}
pii query_part(int l, int r)
{
    pii ret;
    for (int i = l; i <= r; i++)
    {
        bar[a[i]]++;
        ret = max(ret, {bar[a[i]], -b[a[i]]});
    }
    for (int i = l; i <= r; i++)
    {
        bar[a[i]] = 0;
    }
    return ret;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    m = n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        b[i] = a[i];
    }
    sq = sqrt(n);
    for (int i = 1; i <= n; i++)
    {
        bel[i] = (i - 1) / sq + 1;
    }
    tot = bel[n];
    sort(b + 1, b + n + 1);
    int btot = unique(b + 1, b + n + 1) - b - 1;
    for (int i = 1; i <= n; i++)
    {
        a[i] = lower_bound(b + 1, b + btot + 1, a[i]) - b;
    }
    for (int i = 1; i <= m; i++)
    {
        cin >> q[i].l >> q[i].r;
        q[i].id = i;
    }
    sort(q + 1, q + m + 1);
    for (int i = 1, x = 1; i <= tot; i++)
    {
        for (int j = 1; j <= btot; j++)
        {
            cnt[j] = 0;
        }
        int R = min(i * sq, n), l = R + 1, r = R;
        res = {0, 0};
        pii last = {0, 0};
        for (; bel[q[x].l] == i; x++)
        {
            if (bel[q[x].r] == i)
            {
                ans[q[x].id] = -query_part(q[x].l, q[x].r).second;
                continue;
            }
            while (r < q[x].r)
            {
                add(a[++r]);
            }
            last = res;
            while (l > q[x].l)
            {
                add(a[--l]);
            }
            ans[q[x].id] = -res.second;
            while (l <= R)
            {
                cnt[a[l++]]--;
            }
            res = last;
        }
    }
    for (int i = 1; i <= m; i++)
    {
        cout << ans[i] << '\n';
    }
    return 0;
}