BZOJ4241: 历史研究(回滚莫队)

题意

给出$n$个数，每次询问区间$[l, r]$内 每个数*出现次数 的最大值

sol

回滚莫队，名字真萌qwq

考虑如果用正常莫队的话我们是无法删除的，因为一旦删除了最大元素就无法找到次大元素

这时候有人提出了一种新的计算方式

思想很简单：对于每个询问按照左端点的块的编号进行排序，相同的话按又端点排序

然后暴力计算每个块。

如果询问的两个端点在同一个块中，直接暴力计算，时间复杂度$o(\sqrt{n})$

如果不在同一个块中，这时候右端点是不断递增的，因此暴力计算右端点的复杂度为$o(n)$

但是左端点的位置在块内可是飘忽不定的啊qwq

简单，每次询问之后把左端点移动到所在块的最右段即可，每次计算左端点的复杂度为$o(\sqrt{n})$

因为有$\sqrt{n}$个块，因此总的时间复杂度为$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++);//每次询问完之后重新统计答案
        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

*/