「Bzoj 4241」历史研究 (分块/回滚莫队)

发表于 | 分类于 | | + s

BZOJ 4241
题意：有一个长度为$n$的序列，有$m$个询问，每次询问「$[l, r]$内每个数值乘以该数值出现次数」的最大值。

分块做法(在线)：
预处理$s(i,j)$为$i$块到$j$块的答案最优的那个数值是什么，然后像区间众数一样做，询问的时候直接不完整块查询出现次数更新答案，整块就用之前预处理的数值来查询

莫队做法(离线)：
由于删除更新答案不方便，那么这里可以用回滚莫队。按照原莫队方法排序，那么左端点在一块的询问就到了一起，并且右端点单调递增，右端点只有增加，考虑左端点。要使得左端点只能增加，我们把所有在一个块的左端点的询问一起处理，都将莫队中的左端点移到块最右边，每次查询的时候就从最右边开始向左延伸，记录答案，然后再回退到块最右边，这样就避免了删除。一个块处理完后，因为右端点会有删除的情况，所以直接抛弃之前的所有答案，重新从新询问开始记录答案。对于左右端点在同块的询问，直接暴力即可。
时间复杂度分析：
1、对于左右端点在同块的询问，其时间复杂度最坏为$O(m\sqrt n)$
2、在同块中处理时，右端点单调递增，最多增加$n$次，复杂度$O(n\sqrt n)$。左端点回滚，由于在块中，最多滚动$\sqrt n$次，复杂度$O(m\sqrt n)$。
3、对于左端点不同块之间的转换，清除记录数组时间复杂度$O(n\sqrt n)$
由于$m,n$同级，所有算法复杂度为$O(n\sqrt n)$
比分块快多了

分块做法

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 100000 + 5;
int n, q, blolen, ai[MAXN], bl[MAXN], tax1[MAXN], tax[MAXN], whw, s[2000][2000];
vector<int> hh[MAXN];
int cha(int v, int l, int r) {
    return upper_bound(hh[v].begin(), hh[v].end(), r) - upper_bound(hh[v].begin(), hh[v].end(), l - 1);
}
LL query(int l, int r) {
    LL ans = 0;
    if (bl[l] == bl[r]) {
        for (int i = l; i <= r; i++) {
            tax[ai[i]]++;
            if ((LL)tax1[ai[i]] * (LL)tax[ai[i]] > ans) ans = (LL)tax1[ai[i]] * (LL)tax[ai[i]];
        }
        for (int i = l; i <= r; i++) tax[ai[i]] = 0;
    } else {
        ans = (LL)cha(s[bl[l] + 1][bl[r] - 1], l, r) * (LL)tax1[s[bl[l] + 1][bl[r] - 1]];
        for (int i = l; i <= bl[l] * blolen; i++) {
            LL tmp = (LL)cha(ai[i], l, r) * (LL)tax1[ai[i]];
            if (tmp > ans) ans = tmp;
        }
        for (int i = (bl[r] - 1) * blolen + 1; i <= r; i++) {
            LL tmp = (LL)cha(ai[i], l, r) * (LL)tax1[ai[i]];
            if (tmp > ans) ans = tmp;
        }
    }
    return ans;
}
void clean() {
    ms(s, 0);
}
int solve() {
    clean();
    blolen = (int)sqrt((db)n / log2(n));
    for (int i = 1; i <= n; i++) scanf("%d", &ai[i]), tax1[i] = ai[i], bl[i] = (i - 1) / blolen + 1;
    sort(tax1 + 1, tax1 + 1 + n), whw = unique(tax1 + 1, tax1 + 1 + n) - tax1 - 1;
    for (int i = 1; i <= n; i++) ai[i] = lower_bound(tax1 + 1, tax1 + 1 + whw, ai[i]) - tax1, hh[ai[i]].push_back(i);
    bool f = n % blolen;
    for (int i = 1; i <= n / blolen + f; i++) {
        ms(tax, 0);
        int tms = 1;
        for (int j = i; j <= n / blolen + f; j++) {
            s[i][j] = s[i][j - 1];
            for (int k = (j - 1) * blolen + 1; k <= j * blolen; k++) {
                tax[ai[k]]++;
                if ((LL)tax1[s[i][j]] * (LL)tms < (LL)tax[ai[k]] * (LL)tax1[ai[k]]) tms = tax[ai[k]], s[i][j] = ai[k];
            }
        }
    }
    ms(tax, 0);
    while (q--) {
        int l, r; scanf("%d%d", &l, &r);
        printf("%lld\n", query(l, r));
    }
    return 0; 
}
int main() {
    scanf("%d%d", &n, &q), solve();
    return 0;
}

莫队做法

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 100000 + 5;
int blolen, whw, n, q, ai[MAXN], bl[MAXN], tax1[MAXN], tax[MAXN], nl, nr;
LL ans[MAXN], nans;
struct data {
    int l, r, id; 
    bool operator < (const data &b) const {
        if (bl[l] == bl[b.l]) return r < b.r;
        return bl[l] < bl[b.l];
    }
}xw[MAXN];
void clean() {
    nl = 1, nr = 0, nans = 0;
}
int solve() {
    clean(); 
    blolen = (int)sqrt(n);
    for (int i = 1; i <= n; i++) scanf("%d", &ai[i]), tax1[i] = ai[i], bl[i] = (i - 1) / blolen + 1;
    sort(tax1 + 1, tax1 + 1 + n), whw = unique(tax1 + 1, tax1 + 1 + n) - tax1 - 1;
    for (int i = 1; i <= n; i++) ai[i] = lower_bound(tax1 + 1, tax1 + 1 + whw, ai[i]) - tax1;
    for (int i = 1; i <= q; i++) scanf("%d%d", &xw[i].l, &xw[i].r), xw[i].id = i;
    sort(xw + 1, xw + 1 + q);
    ms(tax, 0);
    for (int i = 1; i <= q; i++) {
        if (bl[xw[i].l] != bl[xw[i - 1].l]) nl = bl[xw[i].l] * blolen, nr = nl - 1, nans = 0, ms(tax, 0);
        if (bl[xw[i].l] == bl[xw[i].r]) {
            ans[xw[i].id] = 0;
            for (int j = xw[i].l; j <= xw[i].r; j++) {
                tax[ai[j]]++;
                if ((LL)tax1[ai[j]] * (LL)tax[ai[j]] > ans[xw[i].id]) ans[xw[i].id] = (LL)tax1[ai[j]] * (LL)tax[ai[j]];
            }
            for (int j = xw[i].l; j <= xw[i].r; j++) tax[ai[j]] = 0;
        } else {
            while (nr < xw[i].r) {
                tax[ai[nr + 1]]++; 
                if ((LL)tax1[ai[nr + 1]] * (LL)tax[ai[nr + 1]] > nans) nans = (LL)tax1[ai[nr + 1]] * (LL)tax[ai[nr + 1]];
                nr++;
            }
            LL tmpans = nans;
            while (nl > xw[i].l) {
                tax[ai[nl - 1]]++; 
                if ((LL)tax1[ai[nl - 1]] * (LL)tax[ai[nl - 1]] > tmpans) tmpans = (LL)tax1[ai[nl - 1]] * (LL)tax[ai[nl - 1]];
                nl--;
            }
            while (nl < bl[xw[i].l] * blolen) tax[ai[nl]]--, nl++; 
            ans[xw[i].id] = tmpans;
        }
    }
    for (int i = 1; i <= q; i++) printf("%lld\n", ans[i]);
    return 0; 
}
int main() {
    scanf("%d%d", &n, &q), solve();
    return 0;
}
------ 本文结束 ------