Bzoj 4241(分块/莫队)

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)$
比分块快多了

分块做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#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;
}

莫队做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#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;
}

------ 本文结束 ------