题解：P13984 数列分块入门 9

· · 题解

思路分析

当时学的时候觉得最难的一道题，甚至觉得没法做，不过事实上狭隘了。

首先，我们很套路的将整个序列按照 \sqrt n 的大小分成 \sqrt n 块。然后我们思考众数怎么维护。

不难想到我们可以选择先维护出 [l,r] 的众数。这里的 l,r 不是原序列，而是原序列分出来的块。也就是我们预处理出所有“块段”的众数。显然这样预处理的时间复杂度是 O(n\sqrt n) 的。

直观上讲，一个区间内的众数确实可能会有很多个，我们只取其中的最小的那个是不是有问题呢？这个数不一定是原序列上完整区间的众数！

我们继续思考，假设我们要求的原区间是 [L,R]，对应的“块段”是 [l,r]，如果这个众数不是 [l,r] 这个“块段”的最小众数，那么为了实现块外反超，他必定需要在 [L,blockl_l) 或者 (blockr_r,R] 出现。

因此，可能成为答案的数只可能是中间那一大段的众数，或者边角料上出现的数。出现次数我们可以选择用 vector 维护每个数出现的位置，然后用二分求解。

总时间复杂度 O(n\sqrt n+n\sqrt n\log n)。实际上如果更改一下块长应该是可以把 \log 给挪到根号下面的，不过没有必要。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define sipt
#define sopt
struct IO {
#define mxsz (1 << 21)
    char buf[mxsz], * p1, * p2;
    char pbuf[mxsz], * pp;
    IO() : p1(buf), p2(buf), pp(pbuf) {}
    ~IO() { fwrite(pbuf, 1, pp - pbuf, stdout); }
    inline char gc() {
        if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, mxsz, stdin);
        return p1 == p2 ? ' ' : *p1++;
    }
#ifndef sipt
    inline int read() {
        int r = 0; char c = gc(); while (c < '0' || c>'9') c = gc();
        while (c >= '0' && c <= '9') r = r * 10 + (c ^ 48), c = gc();
        return r;
    }
#else
    inline int read() {
        int r = 0; char c = gc(); bool rev = 0;
        while (c < '0' || c>'9') rev |= (c == '-'), c = gc();
        while (c >= '0' && c <= '9') r = r * 10 + (c ^ 48), c = gc();
        return rev ? ~r + 1 : r;
    }
#endif
    inline void push(const char& c) {
        if (pp - pbuf == mxsz) fwrite(pbuf, 1, mxsz, stdout), pp = pbuf;
        *pp++ = c;
    }
    inline void write(int x) {
        static char sta[22]; int top = 0;
        do sta[top++] = x % 10, x /= 10; while (x);
        while (top) push(sta[--top] ^ 48);
    }
    inline void write(int x, char opc) {
#ifdef sopt
        if (x < 0) push('-'), x = ~x + 1;
#endif
        write(x), push(opc);
    }
} io;
int n, a[300005], sz, mp[550][550], cnt[300005], vp[300005], mv[550][550];
vector<int> v[300005]; map<int, int>nid; int idx, tv[300005];
#define blk(i) ((i) / sz)
inline int sol(int l, int r, int t) {
    return
        upper_bound(v[t].begin(), v[t].end(), r) -
        lower_bound(v[t].begin(), v[t].end(), l);
}
inline int query(int l, int r) {
    int bl = blk(l), br = blk(r), ans = 0, ap = 0;
    if (bl >= br - 1) {
        for (int i = l; i <= r; i++) cnt[a[i]] = 0;
        for (int i = l; i <= r; i++)
            if (++cnt[a[i]] > ans) ans++, ap = a[i];
            else if (cnt[a[i]] == ans && a[i] < ap) ap = a[i];
        return tv[ap];
    } 
    ap = mp[bl + 1][br - 1]; ans = mv[bl + 1][br - 1]; int np;
    for (int i = l; i != (bl + 1) * sz; i++) {
        np = vp[i];
        if (np + ans < v[a[i]].size() && v[a[i]][np + ans] <= r)
            for (;np + ans < v[a[i]].size() && v[a[i]][np + ans] <= r;++ans, ap = a[i]);
        else if (np + ans - 1 < v[a[i]].size() && v[a[i]][np + ans - 1] <= r)
            if (a[i] < ap) ap = a[i];
    }
    for (int i = br * sz; i <= r; i++) {
        np = vp[i];
        if (np - ans >= 0 && v[a[i]][np - ans] >= l)
            for (np = vp[i];np - ans >= 0 && v[a[i]][np - ans] >= l;++ans, ap = a[i]);
        else if (np - ans + 1 >= 0 && v[a[i]][np - ans + 1] >= l)
            if (a[i] < ap) ap = a[i];
    }
    return tv[ap];
}
signed main() {
    ios::sync_with_stdio(0); 
    sz = sqrt(n = io.read());
    for (int i = 0; i != n; i++) nid[a[i] = io.read()] = 0;
    for (auto& v : nid) v.second = ++idx, tv[idx] = v.first;
    for (int i = 0; i != n; i++) a[i] = nid[a[i]];
    for (int i = 0; i != n; i++)
        v[a[i]].push_back(i), vp[i] = v[a[i]].size() - 1;
    for (int i = 0; i <= blk(n - 1); i++) {
        memset(cnt, 0, sizeof cnt);
        for (int j = i; j <= blk(n - 1); j++) {
            mp[i][j] = j ? mp[i][j - 1] : 0; mv[i][j] = j ? mv[i][j - 1] : 0;
            for (int k = j * sz; k != (j + 1) * sz && k != n; k++)
                if (++cnt[a[k]] > mv[i][j]) mv[i][j]++, mp[i][j] = a[k];
                else if (cnt[a[k]] == mv[i][j] && a[k] < mp[i][j]) mp[i][j] = a[k];
        }
    }
    for (int i = 1, l, r; i <= n; i++)
        l = io.read(), r = io.read(),
        io.write(query(l - 1, r - 1), '\n');
}