[洛谷P4168] [Violet]蒲公英

写一篇博客纪念一下第一道AC的黑题~

题目链接

蒲公英

题目分析

神仙分块……做完之后感觉分块比我理解的要深刻很多啊

思路参考洛咕第一篇题解，特别巧妙

首先预处理两个数组：

\(s[i][j]\)：前缀和，前\(i\)（含第\(i\)块）个块中\(j\)的出现次数

\(p[i][j]\)：第\(i\)到\(j\)个块的最小众数

如何预处理：

这一段题解写得比较略……可能是我太弱了，码了半天才从\(O(n^2)\)压成\(O(n \sqrt n)\)的，所以讲细一点

对于\(s[i][j]\)：

第一层循环枚举\(i\)，对于每个\(i\)，先枚举\(j\)将\(i - 1\)的总数转移过来，再扫描本块内的数并累加

对于\(p[i][j]\)：
开一个辅助数组B，记录每个元素出现了多少次

第一层循环枚举\(i\)，第二层循环枚举\(j\)，第三层循环枚举块\(j\)内的每一个元素并累加，每一次\(i\)更改的时候清空B

如何询问：

分两种情况：

• 若\(pos[r]-pos[l]<=1\)，则暴力统计众数并返回答案
• 若\(pos[r] - pos[l] >= 2\)，则对于零散块内的每个元素，先将大块内的出现次数用\(s\)数组前缀和\(O(1)\)处理出来，再暴力统计零散块内的出现次数并更新答案，最后再和大块内的众数（\(p\)数组记录）比较一下即可

代码

#include<bits/stdc++.h>
#define N (100000 + 5)
#define int long long 
using namespace std;
inline int read() {
    int cnt = 0, f = 1; char c = getchar();
    while (!isdigit(c)) {if (c == '-') f = -f; c = getchar();}
    while (isdigit(c)) {cnt = (cnt << 3) + (cnt << 1) + c - '0'; c = getchar();}
    return cnt * f;
}
int n, a[N], b[N], q, t, tmp = 10000000, gmax, m;
int L[305], R[305], pos[N], s[305][N / 2], p[305][N / 2], t0;
int ans, l, r;
int B[N / 2];
inline void Discretize () {
    sort (b + 1, b + n + 1);
    q = unique(b + 1, b + n + 1) - b - 1;
    for (register int i = 1; i <= n; ++i)
        a[i] = lower_bound(b + 1, b + q + 1, a[i]) - b;
}
inline void pre_work() {
    t = sqrt(n) + log(n)/log(2);
    t0 = n / t;
    for (register int i = 1; i <= t; ++i) {
        L[i] = (i - 1) * t0 + 1;
        R[i] = i * t0;
    }
    if (R[t] < n) {
        ++t;
        L[t] = R[t - 1] + 1;
        R[t] = n;
    }
    for (register int i = 1; i <= t; ++i) 
        for (register int j = L[i]; j <= R[i]; ++j) pos[j] = i;
        
    for (register int i = 1; i <= t; ++i) {
        for (register int j = 1; j <= n; ++j) s[i][j] = s[i - 1][j];
        for (register int j = L[i]; j <= R[i]; ++j)
            s[i][a[j]]++;
    }
    for (register int i = 1; i <= t; ++i) {
        memset(B, 0, sizeof(B));
        tmp = 10000000, gmax = 0;
        for (register int j = i; j <= t; ++j) {
            for (register int k = L[j]; k <= R[j]; ++k) {
                B[a[k]]++;
                if (B[a[k]] >= gmax) {
                    if (B[a[k]] > gmax) tmp = a[k];
                    else if (tmp > a[k]) tmp = a[k];
                    gmax = B[a[k]];
                }
            }
            p[i][j] = tmp;
        }
    }
}
 
inline int query(int l, int r) {
    memset(B, 0, sizeof(B));
    int ans = 50000, tmp = 0;
    int x = pos[l], y = pos[r];
    if (x == y || x + 1 == y) {
        for (register int i = l; i <= r; ++i) {
            ++B[a[i]];
            if (B[a[i]] > B[ans]) ans = a[i];
            else if (B[a[i]] == B[ans] && a[i] < ans) ans = a[i];
        }
    } else {
        for (register int i = l; i <= R[x]; ++i) {
            B[a[i]] = (s[y - 1][a[i]] - s[x][a[i]]);
        }
        for (register int i = L[y]; i <= r; ++i) {
            B[a[i]] = (s[y - 1][a[i]] - s[x][a[i]]);
        }
        for (register int i = l; i <= R[x]; ++i) {
            ++B[a[i]];
            if (B[a[i]] > B[ans]) ans = a[i];
            else if (B[a[i]] == B[ans] && a[i] < ans) ans = a[i];
        }
        for (register int i = L[y]; i <= r; ++i) {
            ++B[a[i]];
            if (B[a[i]] > B[ans]) ans = a[i];
            else if (B[a[i]] == B[ans] && a[i] < ans) ans = a[i];
        }
        tmp = p[x + 1][y - 1];
        if (s[y - 1][tmp] - s[x][tmp] > B[ans]) ans = tmp;
        else if ((s[y - 1][tmp] - s[x][tmp] == B[ans]) && tmp < ans) ans = tmp; 
    }
    return b[ans];
}
signed main() {
    n = read(), m = read();
    for (register int i = 1; i <= n; ++i) a[i] = b[i] = read();
    Discretize();
    pre_work(); 
    ans = 0;
    for (register int i = 1; i <= m; ++i){
        l = read(); r = read();
        l = (l + ans - 1) % n + 1, r = (r + ans - 1) % n + 1; 
        if (l > r) swap(l, r);
        ans = query(l, r);
        printf("%lld\n", ans); 
    } 
    return 0;
}

[洛谷P4168] [Violet]蒲公英

原文：https://www.cnblogs.com/kma093/p/11167209.html