[BZOJ2724]蒲公英

题意：Luogu
就是区间众数，强制在线
题解：
先离散化，分块大小\(O(\sqrt{\frac{n}{\log n}})\)(我也不知道怎么来的)
设\(f[i][j]\)表示第\(i,j\)块（包括两端点）的众数，预处理一下
对每个数开一个\(vector\)表示有这个数的位置，来计算任意两点间这个数的出现次数
区间众数显然只能是块间众数或者两遍剩余的块中的某个数
略为卡常
复杂度:\(O(n\sqrt{n})\)

#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
inline void read(int& x)
{
    x=0;char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) x=x*10+c-'0',c=getchar();
}
int n, bsize;
int a[maxn], b[maxn], cnt[maxn], f[1005][1005], belong[maxn];
vector<int> ve[maxn];
inline void init()//块间预处理
{
    int mx, ans;
    register int i,j;
    for (i = 1; i <= belong[n]; ++i)
    {
        memset(cnt, 0, sizeof(cnt));
        mx = 0, ans = 0;
        for (j = (i - 1) * bsize + 1; j <= n; ++j)
        {
            ++cnt[a[j]]; 
            if (cnt[a[j]] > mx || (cnt[a[j]] == mx && b[a[j]] < b[ans]))
                mx = cnt[a[j]], ans = a[j];
            f[i][belong[j]] = ans;
        }
    }
    for (i = 1; i <= n; ++i)//存位置
        ve[a[i]].push_back(i);
}
inline int query2(int l, int r, int k)//求k在[l,r]内出现了多少次
{
    return upper_bound(ve[k].begin(), ve[k].end(), r) - lower_bound(ve[k].begin(), ve[k].end(), l);
}
inline int query(int fr, int to)
{
    int ans, mx, tmp;
    register int i;
    ans = f[belong[fr] + 1][belong[to] - 1];//块间
    mx = query2(fr, to, ans);//块间众数出现次数
    for (i = fr; i <= min(to, belong[fr] * bsize); ++i)
    {
        tmp = query2(fr, to, a[i]);
        if (tmp > mx || (tmp == mx && b[a[i]] < b[ans]))
            mx = tmp, ans = a[i];
    }
    if (belong[fr] ^ belong[to])//if(belong[fr] != belong[to])
        for (i = (belong[to] - 1) * bsize + 1; i <= to; ++i)
        {
            tmp = query2(fr, to, a[i]);
            if (tmp > mx || (tmp == mx && b[a[i]] < b[ans]))
                mx = tmp, ans = a[i];
        }
    return ans;
}
int main()
{
    //freopen("testdata.in", "r", stdin),freopen("testout.out", "w", stdout);
    int y, z, m, x = 0;
    read(n), read(m);
    bsize = sqrt(n / log(n));
    register int i;
    for (i = 1; i <= ((n - 1) / bsize) + 1; ++i)
        for (int j = (i - 1) * bsize + 1; j <= i * bsize; ++j)
            belong[j] = i;
    for (i = 1; i <= n; ++i)
    {
        read(a[i]);
        b[i] = a[i];
    }
    sort(b + 1, b + n + 1);
    int k = unique(b + 1, b + n + 1) - b - 1;
    for (i = 1; i <= n; ++i)
        a[i] = lower_bound(b + 1, b + k + 1, a[i]) - b;
    init();
    for (i = 1; i <= m; ++i)
    {
        read(y); read(z);
        y = (y + x - 1) % n + 1, z = (z + x - 1) % n + 1;
        if (y > z) swap(y, z);
        x = b[query(y, z)];
        printf("%d\n", x);
    }
    return 0;
}

[BZOJ2724]蒲公英

原文：https://www.cnblogs.com/123789456ye/p/12195617.html