题解 [牛客练习赛62 F] 牛牛的繁星

• 牛牛的繁星

题目描述

给定一个长度为 的序列，有 次询问。

每次询问一个区间内，"元素出现次数" 的第 大的 "出现次数"。

强制在线。

正解

如果可以离线，有一个经典的莫队 + 值域分块做法可以做到严格 。（而且常数很小

就直接暴力移动左右端点，移动端点的修改复杂度是 的，然后单次查询是 的。

考虑在线怎么用莫队做。

预处理一些 的桶和分块数组，然后查寻就从最近的 开始移动，查寻完后还原桶和分块数组。

其实可以预处理很多 的，但由于空间原因，最多就只能预处理 个。

然后一次询问就需要移动大约 3000 次，总的复杂度有 ，实现精细一点应该可以通过。

代码

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#define N 100005

using namespace std;

const int B1 = 1000, B2 = 1400;

int n, m, type;

int a[N];
int L[600], R[600];
int rec[600][N], f[600][N], g[600][B1];
int bel[N], bl[105], br[105];

inline int read() {
    int x = 0; char ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
    return x;
}

void getFunc(int l, int r, int *rec, int *f, int *g) {
    f[0] = n, g[0] = n;
    for(int i = l; i <= r; ++i) {
        --f[rec[a[i]]], --g[bel[rec[a[i]]]];
        ++rec[a[i]];
        ++f[rec[a[i]]], ++g[bel[rec[a[i]]]];
    }
}
void move(int l, int r, int ll, int rr, int *rec, int *f, int *g) {
    register int *lp = a + l, *rp = a + r, c;
    while(l > ll) {
        --lp, --l, c = ++rec[*lp];
        --f[c - 1], --g[bel[c - 1]];
        ++f[c], ++g[bel[c]];
    }
    while(r < rr) {
        ++rp, ++r, c = ++rec[*rp];
        --f[c - 1], --g[bel[c - 1]];
        ++f[c], ++g[bel[c]];
    }
    while(l < ll) {
        c = rec[*lp]--, ++lp, ++l;
        --f[c], --g[bel[c]];
        ++f[c - 1], ++g[bel[c - 1]];
    }
    while(r > rr) {
        c = rec[*rp]--, --rp, --r;
        --f[c], --g[bel[c]];
        ++f[c - 1], ++g[bel[c - 1]];
    }
}
int getAns(int *f, int *g, int rem) {
    if(rem > n) return 0;
    for(int i = bel[n]; ~i; --i) {
        if(rem > g[i]) {
            rem -= g[i];
        } else {
            for(int j = br[i]; j >= bl[i]; --j) {
                rem -= f[j];
                if(rem <= 0) return j;
            }
        }
    }
    return -1;
}

int main() {
    n = read(), m = read(), type = read();
    for(int i = 1; i <= n; ++i) a[i] = read();

    for(int i = 0; i <= n; ++i)
        bel[i] = i / B1;
    for(int i = 0; i <= n; ++i)
        br[bel[i]] = i;
    for(int i = n; i >= 0; --i)
        bl[bel[i]] = i;

    int c = 0;
    f[0][0] = g[0][0] = n;
    for(int l = B2; l <= n; l += (B2 << 1))
        for(int r = l + (B2 << 1); r <= n; r += (B2 << 1)) {
            if(r - l <= (B2 << 1)) continue;
            ++c, L[c] = l, R[c] = r;
            getFunc(l, r, rec[c], f[c], g[c]);
        }


    int ans = 0, cnt = 0, o;
    for(int Case = 1, l, r, k; Case <= m; ++Case) {
        l = read(), r = read(), k = read();
        if(type & 1) l = l ^ ans, r = r ^ ans, k = k ^ ans;
        if(r - l <= (B2 << 1)) {
            ++cnt;
            move(l, l - 1, l, r, rec[0], f[0], g[0]);
            ans = getAns(f[0], g[0], k);
            move(l, r, l, l - 1, rec[0], f[0], g[0]);
        } else {
            o = 0;
            for(int i = 1; i <= c; ++i)
                if(!o || abs(l - L[i]) + abs(r - R[i]) < abs(l - L[o]) + abs(r - R[o]))
                    o = i;
            move(L[o], R[o], l, r, rec[o], f[o], g[o]);
            ans = getAns(f[o], g[o], k);
            move(l, r, L[o], R[o], rec[o], f[o], g[o]);
        }
        printf("%d\n", ans);
    }
    return 0;
}