求路过大佬看看这个数据

P4168 [Violet] 蒲公英

Cgod @ 2018-06-03 14:26:27

15 13
96 25 40 2 50 25 48 9 93 43 25 75 86 21 21 
95 83
93 98
71 12
40 71
26 52
30 77
73 47
10 51
19 93
21 53
40 80
56 11
52 25
#include <bits/stdc++.h>
using namespace std;

const int maxn = 40010;
int n, m, block, tot, a[maxn], cnt[maxn][210], f[210][210], tmp[maxn], c[maxn];
int belong[maxn], bl[210], br[210];
vector<int> v;

void init() {
    for (int i = 1; i <= n; i++) {
        cnt[a[i]][belong[i]]++;
    }
    for (int j = 1; j <= belong[n]; j++) {
        for (int i = 1; i <= tot; i++) {
            cnt[i][j] += cnt[i][j - 1];
        }
    }
    for (int i = 1; i <= belong[n]; i++) {
        memset(tmp, 0, sizeof(tmp));
        for (int j = i, cur = 0; j <= belong[n]; j++) {
            for (int k = bl[j]; k <= br[j]; k++) {
                tmp[a[k]]++;
                if (!cur || tmp[a[k]] > tmp[cur] || (tmp[a[k]] == tmp[cur] && a[k] < cur)) {
                    cur = a[k];
                }
            }
            f[i][j] = cur;
        }
    }
}

int query(int l, int r) {
    int res = 0, val = 0;
    if (belong[l] == belong[r] || belong[l] + 1 == belong[r]) {
        for (int i = l; i <= r; i++) {
            c[a[i]] = 0;
        }
        for (int i = l; i <= r; i++) {
            c[a[i]]++;
            if (!res || c[a[i]] > c[res] || (c[a[i]] == c[res] && a[i] < res)) {
                res = a[i];
            }
        }
    } else {
        tot = 0;
        res = f[belong[l] + 1][belong[r] - 1], val = cnt[res][belong[r] - 1] - cnt[res][belong[l]];
        for (int i = l; i <= br[belong[l]]; i++) {
            tmp[++tot] = a[i];
        }
        for (int i = bl[belong[r]]; i <= r; i++) {
            tmp[++tot] = a[i];
        }
        for (int i = 1; i <= tot; i++) {
            c[tmp[i]] = cnt[tmp[i]][belong[r] - 1] - cnt[tmp[i]][belong[l]];
        }
        for (int i = 1; i <= tot; i++) {
            c[tmp[i]]++;
        }
        for (int i = 1; i <= tot; i++) {
            if (!res || c[tmp[i]] > val || (c[tmp[i]] == val && tmp[i] < res)) {
                res = tmp[i];
                val = c[tmp[i]];
            }
        }
        for (int i = 1; i <= tot; i++) {
            c[tmp[i]] = 0;
        }
    }
    return res;
}

int main() {
    scanf("%d %d", &n, &m);
    block = sqrt(n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        belong[i] = (i - 1) / block + 1;
        if (!bl[belong[i]]) {
            bl[belong[i]] = i;
        }
        br[belong[i]] = i;
        v.push_back(a[i]);
    }
    sort(v.begin(), v.end());
    int end = unique(v.begin(), v.end()) - v.begin();
    for (int i = 1; i <= n; i++) {
        a[i] = lower_bound(v.begin(), v.begin() + end, a[i]) - v.begin() + 1;
    }
    tot = n - end;
    init();
    int lastans = 0;
    while (m--) {
        int l, r;
        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 %d\n",l,r);
        printf("%d\n", lastans = v[query(l, r) - 1]);
    }
    return 0;
}

题解里的代码,但我手玩时发现这个运行输出的明显有问题,是我太菜了还是代码有问题???


by Cgod @ 2018-06-03 14:40:35

还有这个,这题数据怕有鬼。。。

13 4
88 40 27 28 19 78 77 53 78 7 58 72 96 
17 27
85 94
39 57
93 23

by hellomath @ 2018-06-03 15:01:24

所以我菜呀!谁能帮我找出问题?


by hellomath @ 2018-06-26 22:52:10

@cx233666 谢谢,现在已更新题解。


by Erina @ 2018-11-04 21:55:34

都过了,但是就是0分


|