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;
}

標籤：C++

上一篇：使用 zeromq與cppzmq 程式退出遇到的坑

下一篇：【Visual Leak Detector】安裝 VLD