关于oi-wiki上的参考代码
查看原帖
关于oi-wiki上的参考代码
464732
luqyou楼主2023/2/2 11:38

为什么这个代码在我本地跑样例跑出来是

8
9
9
16
16

但是洛谷IDE ATcoder 和 Loj 判的样例都是AC??

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
int n, q;
int x[N], t[N], m;

struct Query {
    int l, r, id;
} Q[N];

int pos[N], L[N], R[N], sz, tot;
int cnt[N], __cnt[N];
ll ans[N];

inline bool cmp(const Query &A, const Query &B) {
    if (pos[A.l] == pos[B.l])
        return A.r < B.r;

    return pos[A.l] < pos[B.l];
}

void build() {
    sz = sqrt(n);
    tot = n / sz;

    for (int i = 1; i <= tot; i++) {
        L[i] = (i - 1) * sz + 1;
        R[i] = i * sz;
    }

    if (R[tot] < n) {
        ++tot;
        L[tot] = R[tot - 1] + 1;
        R[tot] = n;
    }
}

inline void Add(int v, ll &Ans) {
    ++cnt[v];
    Ans = max(Ans, 1LL * cnt[v] * t[v]);
}

inline void Del(int v) {
    --cnt[v];
}

int main() {
    scanf("%d %d", &n, &q);

    for (int i = 1; i <= n; i++)
        scanf("%d", &x[i]), t[++m] = x[i];

    for (int i = 1; i <= q; i++)
        scanf("%d %d", &Q[i].l, &Q[i].r), Q[i].id = i;

    build();

    // 对询问进行排序
    for (int i = 1; i <= tot; i++)
        for (int j = L[i]; j <= R[i]; j++)
            pos[j] = i;

    sort(Q + 1, Q + 1 + q, cmp);

    // 离散化
    sort(t + 1, t + 1 + m);
    m = unique(t + 1, t + 1 + m) - (t + 1);

    for (int i = 1; i <= n; i++)
        x[i] = lower_bound(t + 1, t + 1 + m, x[i]) - t;

    int l = 1, r = 0, last_block = 0, __l;
    ll Ans = 0, tmp;

    for (int i = 1; i <= q; i++) {
        // 询问的左右端点同属于一个块则暴力扫描回答
        if (pos[Q[i].l] == pos[Q[i].r]) {
            for (int j = Q[i].l; j <= Q[i].r; j++)
                ++__cnt[x[j]];

            for (int j = Q[i].l; j <= Q[i].r; j++)
                ans[Q[i].id] = max(ans[Q[i].id], 1LL * t[x[j]] * __cnt[x[j]]);

            for (int j = Q[i].l; j <= Q[i].r; j++)
                --__cnt[x[j]];

            continue;
        }

        // 访问到了新的块则重新初始化莫队区间
        if (pos[Q[i].l] != last_block) {
            while (r > R[pos[Q[i].l]])
                Del(x[r]), --r;

            while (l < R[pos[Q[i].l]] + 1)
                Del(x[l]), ++l;

            Ans = 0;
            last_block = pos[Q[i].l];
        }

        // 扩展右端点
        while (r < Q[i].r)
            ++r, Add(x[r], Ans);

        __l = l;
        tmp = Ans;

        // 扩展左端点
        while (__l > Q[i].l)
            --__l, Add(x[__l], tmp);

        ans[Q[i].id] = tmp;

        // 回滚
        while (__l < l)
            Del(x[__l]), ++__l;
    }

    for (int i = 1; i <= q; i++)
        printf("%lld\n", ans[i]);

    return 0;
}
2023/2/2 11:38
加载中...