题解：P13984 数列分块入门 9

· · 题解

一般来说维护这类神奇东西的题目都可以用莫队来做。

不会莫队的可以去 OI Wiki 上看看。

考虑莫队，加入一个数的时候应该怎么做。

设 cnt_i 表示当前区间内值为 i 的数的个数，每次新加入一个元素就在对应的位置上加一，然后和原先答案取更优解就好了。

那删除呢？

当然，一种比较简单的思路是直接用回滚莫队，完全没有思维难度，这里介绍另一种方法——值域分块。

我们对值域进行分块，记 mx_i 表示第 i 个值域块里出现次数最多的值的出现次数，记 buc_{i,j} 表示第 i 个值域块里出现次数为 j 的值的个数，每次加入和删除时在数组上进行相应更新，删除时若此时答案为 x，x所在块为 kx，若删除后 buc_{kx,x}=0 那么就要将答案减一(这里答案指最小众数的出现次数)。

然后得到了最小众数的出现次数后，要得到最小众数，我们先对每个值域块扫过去，取 mx_i 与答案相等的块，然后在块内元素找 cnt_i 与求得的值相等的数即为最终答案。

\large{Code} 
//码风略丑，谨慎观看
#include <bits/stdc++.h>
using namespace std;

inline long long read(void) {
    long long x = 0, f = 1; char c = getchar();
    while (c > '9' || c < '0') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + c - 48, c = getchar();
    return x * f;
}

struct node {
    long long l, r, id;
} query[300005];

long long n, k = 600, cl = 1, cr = 0, qwq[300005], a[300005], s[300005], ans[300005], buc1[1000], buc2[300005], buc3[505][300005], cnt;
map<long long, long long> mp;

bool cmp (node x, node y) {
    if (qwq[x. l] == qwq[y. l]) return (qwq[x. l] & 1) ? (x. r < y. r) : (x. r > y. r);
    return x. l < y. l;
}

int main(void) {
    n = read();
    for (int i = 1; i <= 300000; i++) qwq[i] = (i - 1) / k + 1;
    for (int i = 1; i <= n; i++) a[i] = s[i] = read();
    sort(s + 1, s + 1 + n);
    for (int i = 1; i <= n; i++) if (!mp[s[i]]) mp[s[i]] = ++cnt, s[cnt] = s[i];
    for (int i = 1; i <= n; i++) a[i] = mp[a[i]];
    for (int i = 1; i <= n; i++) query[i]. l = read(), query[i]. r = read(), query[i]. id = i;
    sort(query + 1, query + 1 + n, cmp);
    for (int i = 1; i <= n; i++) {
        while (cr < query[i]. r) {
            cr++;
            buc3[qwq[a[cr]]][buc2[a[cr]]]--;
            buc2[a[cr]]++;
            buc3[qwq[a[cr]]][buc2[a[cr]]]++;
            buc1[qwq[a[cr]]] = max(buc1[qwq[a[cr]]], buc2[a[cr]]);
        }
        while (cl > query[i]. l) {
            cl--;
            buc3[qwq[a[cl]]][buc2[a[cl]]]--;
            buc2[a[cl]]++;
            buc3[qwq[a[cl]]][buc2[a[cl]]]++;
            buc1[qwq[a[cl]]] = max(buc1[qwq[a[cl]]], buc2[a[cl]]);
        }
        while (cl < query[i]. l) {
            if (buc1[qwq[a[cl]]] == buc2[a[cl]] && buc3[qwq[a[cl]]][buc2[a[cl]]] == 1) buc1[qwq[a[cl]]]--;
            buc3[qwq[a[cl]]][buc2[a[cl]]]--;
            buc2[a[cl]]--;
            buc3[qwq[a[cl]]][buc2[a[cl]]]++;
            cl++;
        }
        while (cr > query[i]. r) {
            if (buc1[qwq[a[cr]]] == buc2[a[cr]] && buc3[qwq[a[cr]]][buc2[a[cr]]] == 1) buc1[qwq[a[cr]]]--;
            buc3[qwq[a[cr]]][buc2[a[cr]]]--;
            buc2[a[cr]]--;
            buc3[qwq[a[cr]]][buc2[a[cr]]]++;
            cr--;
        }
        long long nnn = 1;
        for (int j = 2; j <= qwq[300000]; j++) if (buc1[j] > buc1[nnn]) nnn = j;
        for (int j = (nnn - 1) * k + 1; j <= nnn * k; j++)
            if (buc2[j] == buc1[nnn]) {
                ans[query[i]. id] = j;
                break;
            }
    }
    for (int i = 1; i <= n; i++) printf("%lld\n", s[ans[i]]);
    return 0;
}