P3567 [POI2014]KUR-Couriers 题解

· · 题解

看了下题解区，基本上不是主席树就是随机化乱搞……

我寻思着看到这题想到回滚莫队不是很自然吗？？？

我们发现题目有如下特征：

判断是否存在数的出现次数严格大于区间长度的一半，就等价于判断区间里所有数的出现次数最大值是否严格大于区间长度的一半。

出现次数的最大值，是一个在添加过程中易维护，而在删除过程中不易维护的信息。因此我们考虑使用回滚莫队，也就是不删除莫队。

回滚莫队的实现方式及细节不了解的请自行移步模板题，这里不再赘述。

于是这题变成了一道板子题。时间复杂度 O(n\sqrt n)，由于 n,m 同阶统一使用 n。

本人不大会卡常，这题由于数据范围是 5 \times 10^5，在不开 O2 的情况下会 T 掉两个点，开了 O2 之后最大规模测试点在 600ms 内可以跑过。思路放在这里给大家一个参考。

代码：

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 5e5 + 10 , maxm = 5e5 + 10, maxb = 715;
int n, m;
int a[maxn];
struct query {
    int l, r, id;
} q[maxm];
int ans[maxm];
int blen, bnum, bel[maxn];
int cnt[maxn];
int L[maxb], R[maxb];

bool cmp(const query &x, const query &y) { return bel[x.l] != bel[y.l] ? bel[x.l] < bel[y.l] : x.r < y.r; }

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) scanf("%d", a + i);
    for(int i = 1; i <= m; ++i) {
        scanf("%d%d", &q[i].l, &q[i].r);
        q[i].id = i;
    }
    blen = sqrt(n);
    bnum = n / blen;
    for(int i = 1; i <= bnum; ++i) {
        L[i] = (i - 1) * blen + 1;
        R[i] = i * blen;
    }
    if(R[bnum] != n) {
        L[bnum + 1] = R[bnum] + 1;
        R[++bnum] = n;
    }
    for(int i = 1; i <= bnum; ++i) fill(bel + L[i], bel + R[i] + 1, i);
    sort(q + 1, q + m + 1, cmp);
    int l = 1, r = 0, lst = 0, mx, fr;
    for(int i = 1; i <= m; ++i) {
        if(bel[q[i].l] != lst) {
            while(r >= l) --cnt[a[r--]];
            mx = 0; fr = 0;
            lst = bel[q[i].l];
            r = R[lst];
            l = r + 1;
        }
        if(bel[q[i].l] == bel[q[i].r]) {
            for(int j = q[i].l; j <= q[i].r; ++j)
                if(++cnt[a[j]] > mx)
                    mx = cnt[fr = a[j]];
            ans[q[i].id] = mx > (q[i].r - q[i].l + 1) / 2 ? fr : 0;
            for(int j = q[i].l; j <= q[i].r; ++j) --cnt[a[j]];
            mx = 0; fr = 0;
            continue;
        }
        while(r < q[i].r) {
            if(++cnt[a[++r]] > mx)
                mx = cnt[fr = a[r]];
        }
        int lol = l, tmp = mx, ffr = fr;
        while(lol > q[i].l) {
            if(++cnt[a[--lol]] > tmp)
                tmp = cnt[ffr = a[lol]];
        }
        ans[q[i].id] = tmp > (q[i].r - q[i].l + 1) / 2 ? ffr : 0;
        while(lol < l) --cnt[a[lol++]];
    }
    for(int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
    return 0;
}