「BZOJ 2724 && Luogu 4167」[Violet]蒲公英

给出一个长为 n 的数列，以及 m 个操作，操作涉及询问区间的最小众数。

Luogu

分析

这题和分块入门9一样的操作。

一开始直接把我分块9的代码蒯下来根据题目改了一下，结果测样例发现不对......然后懵逼，找不出错误啊......接着就干脆重新写，想到刚写的 作诗 ，便写了一个用 map 离散化，然后用后缀和来求的方法，结果调了一节晚自习都没调出来(气到想骂人)......真的没找到哪里错了，样例是过了，但是提交 0pts .......

看了很多题解，大多是用 vetor ，少数后缀和的也写的和我不一样，但不想把一晚上都用在这道 sb 题上，只好又把分块9的代码蒯了，然后改，还是不对，又去对着 hzwer 大佬的代码改，也不对？最后想起要 if (l > r) swap(l, r) ，然后就过了样例(真不容易)，但提交超时了......于是卡常+吸氧，过了。

代码

首先是我没调出来的 0 分代码：

//=========================
//  author:hliwen
//  date:2020.1.15
//=========================
#include <map>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 40005
#define il inline
#define re register
#define tie0 cin.tie(0),cout.tie(0)
#define fastio ios::sync_with_stdio(false)
#define File(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)
using namespace std;
typedef long long ll;

template <typename T> inline void read(T &x) {
    T f = 1; x = 0; char c;
    for (c = getchar(); !isdigit(c); c = getchar()) if (c == '-') f = -1;
    for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x *= f;
}

int n, m, blo, tot;
int a[N], bl[N], v[N], num[N];
int mx[505][505], f[505][505], cnt[505][N];

map <int, int> mp;

int calc(int l, int r, int x) {
    return cnt[l][x] - cnt[r+1][x];
}

int query(int l, int r) {
    memset(num, 0, sizeof num);
    int ret = f[bl[l]+1][bl[r]-1];
    if (bl[l] != bl[r]) {
        num[ret] = mx[bl[l]+1][bl[r]-1];
        for (int i = l; i <= bl[l] * blo; ++i) {
            if (!num[a[i]]) num[a[i]] = calc(bl[l] + 1, bl[r] - 1, a[i]);
            num[a[i]]++;
            if ((num[a[i]] > num[ret]) || (num[a[i]] == num[ret] && v[a[i]] < v[ret]))
                ret = a[i];
        }
        for (int i = (bl[r] - 1) * blo + 1; i <= r; ++i) {
            if (!num[a[i]]) num[a[i]] = calc(bl[l] + 1, bl[r] - 1, a[i]);
            num[a[i]]++;
            if ((num[a[i]] > num[ret]) || (num[a[i]] == num[ret] && v[a[i]] < v[ret]))
                ret = a[i];
        }
    }
    else {
        ret = 0;
        for (int i = l; i <= r; ++i) {
            num[a[i]]++;
            if (num[a[i]] > num[ret] || (num[a[i]] == num[ret] && v[a[i]] < v[ret]))
                ret = a[i];
        }
    }
    return ret;
}

int main() {
    File("P4168_1");
    int l, r, ans = 0;
    read(n), read(m);
    blo = sqrt(n);
    for (int i = 1; i <= n; ++i) {
        read(a[i]);
        bl[i] = (i - 1) / blo + 1;
        if (!mp[a[i]]) {
            mp[a[i]] = ++tot;
            v[tot] = a[i];
        }
        a[i] = mp[a[i]];
        for (int j = 1; j <= bl[i]; ++j) {
            cnt[j][a[i]]++;
            if (cnt[j][a[i]] > mx[j][bl[i]]) {
                mx[j][bl[i]] = cnt[j][a[i]];
                f[j][bl[i]] = a[i];
            }
            else if (cnt[j][a[i]] == mx[j][bl[i]] && v[a[i]] < v[f[j][bl[i]]])
                f[j][bl[i]] = a[i];
        }
    }
    for (int i = 1; i <= m; ++i) {
        read(l), read(r);
        l = (l + ans - 1) % n + 1, r = (r + ans - 1) % n + 1;
        if (l > r) swap(l, r);
        printf("%d\n", ans = v[query(l, r)]);
    }
    return 0;
}

然后是和分块9几乎一样的吸氧代码：

//=========================
//  author:hliwen
//  date:2020.1.15
//=========================
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include <map>
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 40005
#define il inline
#define re register
#define tie0 cin.tie(0),cout.tie(0)
#define fastio ios::sync_with_stdio(false)
#define File(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)
using namespace std;
typedef long long ll;

template <typename T> inline void read(T &x) {
    T f = 1; x = 0; char c;
    for (c = getchar(); !isdigit(c); c = getchar()) if (c == '-') f = -1;
    for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x *= f;
}

int n, m, tot;
int a[N], bl[N], v[N], cnt[N], f[505][505];

map <int, int> mp;
vector <int> ve[N];

il void pre(int x) {
    re int num = 0, ret = 0;
    memset(cnt, 0, sizeof cnt);
    for (re int i = (x - 1) * m + 1; i <= n; ++i) {
        cnt[a[i]]++;
        if (cnt[a[i]] > num) ret = a[i], num = cnt[a[i]];
        else if (cnt[a[i]] == num && v[a[i]] < v[ret]) ret = a[i];
        f[x][bl[i]] = ret;
    }
}

il int calc(int l, int r, int x) {
    return upper_bound(ve[x].begin(), ve[x].end(), r) - lower_bound(ve[x].begin(), ve[x].end(), l);
}

il int query(int l, int r) {
    re int ret, num;
    ret = f[bl[l] + 1][bl[r] - 1], num = calc(l, r, ret);
    for (re int i = l; i <= min(bl[l] * m, r); ++i) {
        re int t = calc(l, r, a[i]);
        if (t > num) ret = a[i], num = t;
        else if (t == num && v[ret] > v[a[i]]) ret = a[i];
    }
    if (bl[l] != bl[r]) {
        for (re int i = (bl[r] - 1) * m + 1; i <= r; ++i) {
            re int t = calc(l, r, a[i]);
            if (t > num) ret = a[i], num = t;
            else if (t == num && v[ret] > v[a[i]]) ret = a[i];
        }
    }
    return ret;
}

int main() {
    re int l, r, x = 0, q;
    read(n), read(q);
    m = sqrt(n);
    for (re int i = 1; i <= n; ++i) {
        read(a[i]);
        bl[i] = (i - 1) / m + 1;
        if (!mp[a[i]]) {
            mp[a[i]] = ++tot;
            v[tot] = a[i];
        }
        a[i] = mp[a[i]], ve[a[i]].push_back(i);
    }
    for (re int i = 1; i <= bl[n]; ++i) pre(i);
    for (re int i = 1; i <= q; ++i) {
        read(l), read(r);
        l = (l + x - 1) % n + 1, r = (r + x - 1) % n + 1;
        if (l > r) swap(l, r);
        printf("%d\n", x = v[query(l, r)]);
    }
    return 0;
}

「BZOJ 2724 && Luogu 4167」[Violet]蒲公英

原文：https://www.cnblogs.com/hlw1/p/12198899.html