BZOJ4241: Historical Research (rolling back team Mo)

meaning of the title

Give the number of $n $, the maximum value of each number * occurrence times within $[L, R] $of each query interval

Sol

Roll back team Mo, whose name is Zhenmeng qwq

Consider that if we use normal Mo team, we can't delete it, because once we delete the largest element, we can't find the next largest element

At this time, someone put forward a new calculation method

The idea is simple: for each query, it is sorted according to the number of the block at the left end point, and if it is the same, it is sorted according to the end point

Then violence counts each block.

If the two endpoints of the query are in the same block, direct brute force calculation, time complexity $O(\sqrt{n})$

If it is not in the same block, the right endpoint is increasing, so the complexity of violence calculation is $O(n)$

But the position of the left end is in the block, but it's erratic

Simply, move the left endpoint to the rightmost segment of the block after each query. The complexity of calculating the left endpoint is $O(\sqrt{n})$

Because there are $\ sqrt{n} $blocks, the total time complexity is $O(\sqrt{n}n)$

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#define LL long long 
using namespace std;
const int MAXN = 1e5 + 10, INF = 1e9 + 7;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, Q;
LL out[MAXN], ans;
int be[MAXN], date[MAXN], cnt[MAXN], a[MAXN], tot, base, num;
struct Query {
    int l, r, id;
    bool operator < (const Query &rhs) const {
        return be[l] == be[rhs.l] ? r < rhs.r : be[l] < be[rhs.l];
    }
}q[MAXN];
LL solve(int l, int r) {
    static int tim[MAXN]; LL ans = 0;
    for(int i = l; i <= r; i++) tim[a[i]] = 0;
    for(int i = l; i <= r; i++) tim[a[i]]++, ans = max(ans, 1ll * tim[a[i]] * date[a[i]]);
    return ans;
}
void Add(int x) {
    cnt[a[x]]++;
    ans = max(ans, 1ll * cnt[a[x]] * date[a[x]]);
}
void Del(int x) {
    cnt[a[x]]--;
}
int Get(int i, int id) {
    int R = min(N, id * base), ql = R + 1, qr = ql - 1; ans = 0;
    memset(cnt, 0, sizeof(cnt));
    for(; be[q[i].l] == id; i++) {
        if(be[q[i].l] == be[q[i].r]) {out[q[i].id] = solve(q[i].l, q[i].r); continue;}
        while(qr < q[i].r) Add(++qr);
        LL cur = ans;
        while(ql > q[i].l) Add(--ql);
        out[q[i].id] = ans;
        while(ql < R + 1) Del(ql++);//Count the answers again after each inquiry
        ans = cur;
    }
    return i;
}
main() {
    //freopen("4241.in", "r", stdin);
    //freopen("4241.out", "w", stdout);
    N = read(); Q = read(); base = sqrt(N);
    for(int i = 1; i <= N; i++) {
        a[i] = date[i] = read(); be[i] = (i - 1) / base + 1;
        num = max(num, be[i]);
    }

    sort(date + 1, date + N + 1);
    int tot = unique(date + 1, date + N + 1) - date - 1;
    for(int i = 1; i <= N; i++) a[i] = lower_bound(date + 1, date + N + 1, a[i]) - date;

    for(int i = 1; i <= Q; i++) q[i].l = read(), q[i].r = read(), q[i].id = i;
    sort(q + 1, q + Q + 1);

    for(int i = 1, id = 1; id <= num; id++) 
        i = Get(i, id);
    

    for(int i = 1; i <= Q; i++)
        printf("%lld\n", out[i]);
    return 0;
}
/*
2
3 2
1 2 3
2 2
1 3
3 2
1 2 3
2 2
1 3

*/

Tags: C++

Posted on Mon, 06 Jan 2020 01:20:25 -0800 by bloodgoat