P5048 [Ynoi2019 模拟赛] Yuno loves sqrt technology III

题目-P5048 [Ynoi2019 模拟赛] Yuno loves sqrt technology III

问题分析

查询区间众数出现的次数, 尝试对区间进行分块

假设已经知道了区间内众数出现的次数$s$, 那么只需要判断散列块中是否有哪个数字还能成为众数

对于每个数字记录出现的位置$v$, $v[a[i]]$代表$a[i]$出现的一些位置, $pos[i]$代表$a[i]$在$v[a[i]]$中的索引

假设区间内众数出现的次数是$ans$

• 枚举所有左侧散列块, 假设数值是$w$, 那么只需要检查是否存在$v[w][pos[i]+ans]\le r$, 就可以更新$ans$, 也就是算上当前位置, $w$出现的次数是$ans+1$
• 枚举右侧散列块, 假设数值是$w$, 检查$v[w][pos[i]-ans]\ge l$, 算上当前位置, $w$出现的次数是$ans+1$

算法步骤

• 初始化分块, 对数据进行离散化
• 暴力初始化$f$数组

代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 10, M = 710;

int n, m, a[N];
vector<int> vec;
int bsize, bcnt, st[M], ed[M], b[N];
vector<int> v[N];
int pos[N], f[M][M], tot[N];

void init() {
   
    bsize = sqrt(n);
    bcnt = (n - 1) / bsize + 1;
    for (int i = 1; i <= bcnt; ++i) {
   
        st[i] = (i - 1) * bsize + 1;
        ed[i] = min(n, i * bsize);
    }
    for (int i = 1; i <= n; ++i) b[i] = (i - 1) / bsize + 1;
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
}

int find(int x) {
   
    return lower_bound(vec.begin(), vec.end(), x) - vec.begin();
}

int query(int l, int r) {
   
    int x = b[l], y = b[r];
    if (x == y) {
   
        int ans = 0;
        for (int i = l; i <= r; ++i) tot[a[i]] = 0;
        for (int i = l; i <= r; ++i) ans = max(ans, ++tot[a[i]]);
        return ans;
    }

    int ans = f[x + 1][y - 1];
    for (int i = l; i <= ed[x]; ++i) {
   
        int t = pos[i];
        if (i + t < v[a[i]].size() && v[a[i]][i + t] <= r) ans++;
    }
    for (int i = st[y]; i <= r; ++i) {
   
        int t = pos[i];
        if (t - ans >= 0 && v[a[i]][t - ans] >= l) ans++;
    }

    return ans;
}

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

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i], vec.push_back(a[i]);
    init();

    for (int i = 1; i <= n; ++i) a[i] = find(a[i]);
    for (int i = 1; i <= n; ++i) {
   
        v[a[i]].push_back(i);
        pos[i] = v[a[i]].size();
        pos[i]--;
    }

    for (int i = 1; i <= bcnt; ++i) {
   
        memset(tot, 0, sizeof tot);
        for (int j = i; j <= bcnt; ++j) {
   
            f[i][j] = f[i][j - 1];
            for (int k = st[j]; k <= ed[j]; ++k) {
   
                f[i][j] = max(f[i][j], ++tot[a[k]]);
            }
        }
    }

    int last = 0;
    while (m--) {
   
        int l, r;
        cin >> l >> r;
        l ^= last, r ^= last;
        if (r < l) swap(l, r);
        int ans = query(l, r);
        cout << ans << '\n';
        last = ans;
    }

    return 0;
}