Acwing249蒲公英

[洛谷]([Violet]蒲公英 - 洛谷)

[Acwing(数据较强)](249. 蒲公英 - AcWing题库)

前言

“好诗意的题目啊......

那就用很诗意的代码写吧”

思路

首先， 这题是给你 \(l, r\) 的限制目的是强制在线，所以莫队啥的不能用。

由于不满足“区间可加性”（已知\([l, r] \cup[r+1,k]\) 的众数，不能得出 \([l, k]\) 的众数）， 所以树状数组/线段树就很难维护。

考虑分块，首先离散。 设块的长度为 \(T\) , 则有 \(n / T\) 块， 然后预处理第 \(i\) 到 \(j\) 块的众数以及数的出现次数， 这段时间复杂度 \(O(NT^2)\)。 之后两段暴力维护, \(O(N/T)\)

总的时间复杂度 \(O(NT^2 + MN/T)\)

所以如果 \(T=\sqrt{N}\) 时间复杂度就为 \(O(N\sqrt{N})\) ( \(N,M\) 同阶)

#include <bits/stdc++.h>
#define for_(i,a,b) for (int i = (a); i < (b); i++)
#define rep_(i,a,b) for (int i = (a); i <= (b); i++)
#define _Pos(i, j) (((i)-1)*cnt+(j))
using namespace std;
const int maxn = 4e5 + 10, mod = 1e9 + 7;// mod = 1949777;
const double EPS = 1e-3;
int n, m, t, cnt;
int a[maxn], id[maxn], l[maxn], r[maxn], b[maxn], s[maxn];
void solve() {
}
signed main() {
#ifdef LOCAL
    freopen("w.in", "r", stdin);
    freopen("w.ans", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;

    //
    while (t * t * t < n)
        t++;

    t--; //
    t = n / t; //the lenth of a bar
    //
    rep_(i, 1, n) {
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b + 1, b + 1 + n);
    int len = unique(b + 1, b + 1 + n) - b - 1;
    rep_(i, 1, n) {
        a[i] = lower_bound(b + 1, b + 1 + len, a[i]) - b;
    }

    //
    for (int i = 1; i <= n / t; i++) {
        l[i] = (i - 1) * t + 1;
        r[i] = i * t;
    }

    cnt = n / t;

    if (r[cnt] < n) {
        l[cnt + 1] = r[cnt] + 1;
        r[cnt + 1] = n;
        cnt++;
    }

    for (int i = 1; i <= cnt; i++) {
        for (int j = l[i]; j <= r[i]; j++) {
            id[j] = i;
        }
    }

    vector<vector<int>> v(cnt * cnt + 1, vector<int>(n, 0));

    //
    for (int i = 1; i <= cnt; i++) {
        for (int j = i; j <= cnt; j++) {
            for (int k = l[i]; k <= r[j]; k++) {
                v[_Pos(i, j)][a[k]]++;
            }

            int mx = 0, _S = 0;

            for (int k = 1; k <= n; k++) {
                if (mx < v[_Pos(i, j)][k] || mx == v[_Pos(i, j)][k] && _S > k) {
                    mx = v[_Pos(i, j)][k];
                    _S = k;
                }
            }

            s[_Pos(i, j)] = _S;
        }
    }

    //
    vector<int> N(n + 1, 0);
    int _X = 0;

    for (int i = 1, L, R; i <= m; i++) {
        cin >> L >> R;
        L = (L + _X - 1) % n + 1, R = (R + _X - 1) % n + 1;

        if (L > R)
            swap(L, R);

        int mx = 0, _S = 0;

        if (id[L] == id[R]) {
            for (int j = L; j <= R; j++) {
                N[a[j]]++;

                if (mx < N[a[j]] || mx == N[a[j]] && _S > a[j])
                    mx = N[a[j]], _S = a[j];
            }
        } else {
            // Left
            for (int j = L; id[j] == id[L]; j++) {
                N[a[j]]++;

                if (N[a[j]] == 1) {
                    if (id[L] + 1 < id[R]) {
                        N[a[j]] += v[_Pos(id[L] + 1, id[R] - 1)][a[j]];
                    }
                }

                if (mx < N[a[j]] || mx == N[a[j]] && _S > a[j])
                    mx = N[a[j]], _S = a[j];
            }

            // Right
            for (int j = R; id[j] == id[R]; j--) {
                N[a[j]]++;

                if (N[a[j]] == 1) {
                    if (id[L] + 1 < id[R]) {
                        N[a[j]] += v[_Pos(id[L] + 1, id[R] - 1)][a[j]];
                    }
                }

                if (mx < N[a[j]] || mx == N[a[j]] && _S > a[j])
                    mx = N[a[j]], _S = a[j];
            }

            // Mid
            if (id[L] + 1 < id[R] && N[s[_Pos(id[L] + 1, id[R] - 1)]] == 0) {
                int _O = s[_Pos(id[L] + 1, id[R] - 1)];
                int Tmp = v[_Pos(id[L] + 1, id[R] - 1)][_O];

                if (mx < Tmp || mx == Tmp && _S > _O) {
                    mx = Tmp;
                    _S = _O;
                }
            }
        }

        _X = b[_S];
        cout << _X << endl;

        // clear
        for (int j = L; id[j] == id[L]; j++)
            N[a[j]] = 0;

        for (int j = R; id[j] == id[R]; j--)
            N[a[j]] = 0;
    }

    return 0;
}