P4168 [Violet] 蒲公英 题解

· · 题解

题意

给定一个长度为 n 的序列，每个位置有一个颜色。每次询问一个区间中出现次数最多的颜色，如果有多个则取颜色数字最小的。强制在线

题解

首先离散化。然后考虑用数据结构去维护这个序列。

线段树不好维护，考虑分块。

为了快速访问块中某一颜色出现的次数，用 cnt_{i, j} 表示前 1 到 i 块中，颜色 j 出现的次数。

然后询问的时候，用 tot_i 表示颜色 i 在这段区间出现的次数。对于整块，用 cnt 存进 tot即可；对于散块，直接暴力加进来就可以。

答案就在更新 tot 的时候一同更新即可。时间复杂度 \mathcal{O}(n \sqrt{n})。

CODE：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

const int maxn = 4e4 + 5;

int n, m, Q, px, mx, lastans;
int a[maxn], b[maxn], blk[maxn], L[205], R[205];
int cnt[205][maxn], tot[maxn];

void add(int x, int val) {
    tot[x] += val;
    if(tot[x] >= tot[mx]) {
        if(tot[x] > tot[mx]) mx = x;
        else if(x < mx) mx = x;
    }
}

void prework() {
    for(int i = 1; i <= blk[n]; i++) {
        for(int j = 1; j <= px; j++)
            cnt[i][j] = cnt[i-1][j];
        for(int j = L[i]; j <= R[i]; j++)
            cnt[i][a[j]]++;
    }
}

int getans(int l, int r) {
    if(blk[l] == blk[r]) {
        for(int i = l; i <= r; i++) tot[a[i]] = 0;
        mx = px+1;
        for(int i = l; i <= r; i++)
            add(a[i], 1);
        return mx;
    }
    for(int i = 1; i <= px; i++) tot[i] = 0;
    mx = px+1;
    int pl = blk[l] + 1, pr = blk[r] - 1;
    if(pl <= pr) for(int i = 1; i <= px; i++) 
        add(i, cnt[pr][i] - cnt[pl-1][i]);
    for(int i = l; i <= R[blk[l]]; i++)
        add(a[i], 1);
    for(int i = L[blk[r]]; i <= r; i++)
        add(a[i], 1);
    return mx;
}

int main() {
    scanf("%d %d", &n, &m);
    Q = sqrt(n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        blk[i] = (i-1)/Q + 1;
        if(blk[i]*Q == i) R[blk[i]] = i;
        if(blk[i-1]*Q == i-1) L[blk[i]] = i;
        b[i] = a[i];
    }
    R[blk[n]] = n;
    sort(b+1, b+1+n);
    px = unique(b+1, b+1+n) - b - 1;
    for(int i = 1; i <= n; i++)
        a[i] = lower_bound(b+1, b+1+px, a[i]) - b;

    prework();
    for(int i = 1, l, r; i <= m; i++) {
        scanf("%d %d", &l, &r);
        l = (l + lastans - 1) % n + 1;
        r = (r + lastans - 1) % n + 1;
        if(l > r) swap(l, r);
        printf("%d\n", lastans = b[getans(l, r)]);
    }
    return 0;
}