「Bzoj 2724」[Violet 6] 蒲公英(分块)

BZOJ 2724
题意：强制在线不修改求区间众数。
如果不强制在线，可以离线莫队直接处理。
这里强制在线，我们将原数列分块，预处理$i$块到$j$块区间的众数，直接开桶统计，用于求解整块的区间。
用vector把相同的数的位置按顺序存储下来，求众数可以用询问区间的每个数字去求他出现次数，比较即可。
对于整块，我们预处理了$i$块到$j$块区间的众数，直接询问这个数字在询问区间出现次数即可；
对于不完整的块，我们暴力每个数字在询问区间出现次数即可
最后输出即可，时间复杂度$O(m \cdot logn+\frac nm)$, 其中$n$为数列长，$m$为每个块长，根据均值不等式，在$m \cdot logn=\frac nm$时和有最小值，$m=\sqrt{\frac{n}{logn}}$，即得到最优分块大小

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 40000 + 5;
int n, q, whw, ai[MAXN], key = 0, tax[MAXN], tax1[MAXN], blolen, bl[MAXN], s[1005][1005];
vector<int> hh[MAXN];
int cx(int v, int x, int y) {
    return upper_bound(hh[v].begin(), hh[v].end(), y) - upper_bound(hh[v].begin(), hh[v].end(), x - 1);
}
int query(int x, int y) {
    int mks = cx(s[bl[x] + 1][bl[y] - 1], x, y), ret = s[bl[x] + 1][bl[y] - 1];
    for (int i = x; i <= min(y, bl[x] * blolen); i++) {
        int tmp = cx(ai[i], x, y);
        if (tmp > mks) ret = ai[i], mks = tmp; else if (tmp == mks && ai[i] < ret) ret = ai[i];
    }
    if (bl[x] != bl[y]) for (int i = (bl[y] - 1) * blolen + 1; i <= y; i++) {
        int tmp = cx(ai[i], x, y);
        if (tmp > mks) ret = ai[i], mks = tmp; else if (tmp == mks && ai[i] < ret) ret = ai[i];
    }
    return ret;
}
void clean() {}
int solve() {
    clean();
    blolen = (int)sqrt((db)n / log2(n));
    for (int i = 1; i <= n; i++) scanf("%d", &ai[i]), tax1[i] = ai[i], bl[i] = (i - 1) / blolen + 1;
    sort(tax1 + 1, tax1 + 1 + n), whw = unique(tax1 + 1, tax1 + 1 + n) - tax1 - 1;
    for (int i = 1; i <= n; i++) ai[i] = lower_bound(tax1 + 1, tax1 + 1 + whw, ai[i]) - tax1, hh[ai[i]].push_back(i);
    bool f = n % blolen;
    for (int i = 1; i <= n / blolen + f; i++) {
        ms(tax, 0); int mks = 0;
        for (int j = i; j <= n / blolen + f; j++) {
            s[i][j] = s[i][j - 1];
            for (int k = (j - 1) * blolen + 1; k <= min(n, j * blolen); k++) {
                tax[ai[k]]++;
                if (tax[ai[k]] > mks) mks = tax[ai[k]], s[i][j] = ai[k]; else if (tax[ai[k]] == mks && ai[k] < s[i][j]) s[i][j] = ai[k];
            }
        }
    }
    while (q--) {
        int l, r;
        scanf("%d%d", &l, &r);
        l = (l + key - 1) % n + 1, r = (r + key - 1) % n + 1;
        if (l > r) swap(l, r);
        printf("%d\n", key = tax1[query(l, r)]);
    }
    return 0; 
}
int main() {
    scanf("%d%d", &n, &q), solve();
    return 0;
}