[数据结构与算法]Codeforces 840D 回滚莫队

题意

传送门 Codeforces 840D Destiny

题解

区间中严格大于 $(r?l+1)/k$ 的数不超过 $k?1$ 个，维护区间最大的 $k?1$ 个数即可。区间新增元素可以 $O(k)$ 地维护最大的 $k?1$ 个数，删除操作可能要使用基于值域维护的数据结构，效率不如新增操作。应用不带删除的回滚莫队即可，总时间复杂度 $O(kn\sqrt{n})$。

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int MAXN = 3E5 + 5, INF = 0x3f3f3f3f, SZ = 4;
int N, Q, A[MAXN];
int idx[MAXN], L[MAXN], R[MAXN];
int cnt[MAXN], _cnt[MAXN], res[MAXN];
struct node
{
    int l, r, k, id;
    bool operator<(const node &o)
    {
        if (idx[l] != idx[o.l])
            return idx[l] < idx[o.l];
        return r < o.r;
    }
} qs[MAXN];

int ask(int d, vector<int> &rec, int cnt[])
{
    int res = INF;
    for (int x : rec)
        if (cnt[x] > d)
            res = min(res, x);
    return res == INF ? -1 : res;
}

void add(int k, vector<int> &rec, int cnt[])
{
    int x = A[k];
    ++cnt[x];
    for (int y : rec)
        if (y == x)
            return;
    int pos = -1;
    for (int i = 0; i < rec.size(); ++i)
        if (pos == -1 || cnt[rec[pos]] > cnt[rec[i]])
            pos = i;
    if (rec.size() < SZ)
        rec.pb(x);
    else if (cnt[rec[pos]] < cnt[x])
        rec[pos] = x;
}

void del(int k, int cnt[]) { --cnt[A[k]]; }

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> N >> Q;
    for (int i = 0; i < N; ++i)
        cin >> A[i];
    for (int i = 0; i < Q; ++i)
    {
        auto &q = qs[i];
        cin >> q.l >> q.r >> q.k;
        --q.l;
        q.id = i;
    }
    int sz = sqrt(N) + 1;
    for (int l = 0, i = 0; l < N; l += sz, ++i)
    {
        L[i] = l, R[i] = min(l + sz, N);
        for (int j = L[i]; j < R[i]; ++j)
            idx[j] = i;
    }
    sort(qs, qs + Q);
    vector<int> rec;
    for (int i = 0, l = 0, r = 0, pre = -1; i < Q; ++i)
    {
        int ql = qs[i].l, qr = qs[i].r, qk = qs[i].k;
        if (idx[ql] == idx[qr - 1])
        {
            vector<int> _rec;
            for (int j = ql; j < qr; ++j)
                add(j, _rec, _cnt);
            res[qs[i].id] = ask((qr - ql) / qk, _rec, _cnt);
            for (int j = ql; j < qr; ++j)
                del(j, _cnt);
            continue;
        }
        if (idx[ql] != pre)
        {
            pre = idx[ql];
            int b = R[idx[ql]];
            while (b < l)
                add(--l, rec, cnt);
            while (r < b)
                add(r++, rec, cnt);
            while (l < b)
                del(l++, cnt);
            while (b < r)
                del(--r, cnt);
            rec.clear();
        }
        while (r < qr)
            add(r++, rec, cnt);
        auto _rec = rec;
        int _l = l;
        while (ql < _l)
            add(--_l, _rec, cnt);
        res[qs[i].id] = ask((qr - ql) / qk, _rec, cnt);
        while (_l < l)
            del(_l++, cnt);
    }
    for (int i = 0; i < Q; ++i)
        cout << res[i] << '\n';
    return 0;
}