[Codeforces700D] Huffman Coding on Segment

做法

想了挺久只会胡个 \(\mathcal O(n \sqrt n \log n)\) 的莫队 + 维护 huffman 树,去看了眼别人的题解发现也有是这个复杂度的.....不过比我胡的妙多了,下面写的是看到的别人的做法。

用莫队处理询问,维护下每个数出现几次,并记录下当前出现次数大于 \(x\) 的数。对次数不超过 \(x\) 的数,记一下每个数出现几次然后 \(\mathcal O(x)\) 算出合并代价。转化为只有出现次数超过 \(x\) 的数的情况,这时最多只有 \(\frac n x\) 个数,贪心合并即可。询问时间复杂度为 \(\mathcal O(x + \frac n x \log n)\),取 \(x = \sqrt {n \log n}\),则一次询问的复杂度为 \(\sqrt {n \log n}\)

莫队维护出现次数大于 \(x\) 的数时可以使用链表,这样的话莫队的复杂度为 \(\mathcal 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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <bits/stdc++.h>

using namespace std;

const int maxn = 100010;
const int sqr = int (sqrt(maxn) * 20);
const int _sqr = int (sqrt(maxn));

int n, q;
int a[maxn], ql[maxn], qr[maxn];
int ind[maxn], ans[maxn], cnt[maxn], cc[maxn], ncnt[maxn];
list<int> st;
list<int>::iterator p[maxn];

int cmp(int x, int y) {
if (ql[x] / _sqr == ql[y] / _sqr) return qr[x] < qr[y];
return ql[x] < ql[y];
}

int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
scanf("%d", &q);
for (int i = 1; i <= q; i++) scanf("%d%d", &ql[i], &qr[i]);
for (int i = 1; i <= q; i++) ind[i] = i;
sort(ind + 1, ind + q + 1, cmp);
int curl = 1, curr = 0;
cc[0] = 100000;
for (int _ = 1; _ <= q; _++) {
int x = ind[_];
int l = ql[x], r = qr[x];
while (curl > l) {
-- curl;
-- cc[cnt[a[curl]]];
if (cnt[a[curl]] >= sqr) st.erase(p[a[curl]]);
++ cnt[a[curl]];
if (cnt[a[curl]] >= sqr) p[a[curl]] = st.insert(st.end(), cnt[a[curl]]);
++ cc[cnt[a[curl]]];
}
while (curr < r) {
++ curr;
-- cc[cnt[a[curr]]];
if (cnt[a[curr]] >= sqr) st.erase(p[a[curr]]);
++ cnt[a[curr]];
if (cnt[a[curr]] >= sqr) p[a[curr]] = st.insert(st.end(), cnt[a[curr]]);
++ cc[cnt[a[curr]]];
}
while (curl < l) {
-- cc[cnt[a[curl]]];
if (cnt[a[curl]] >= sqr) st.erase(p[a[curl]]);
-- cnt[a[curl]];
if (cnt[a[curl]] >= sqr) p[a[curl]] = st.insert(st.end(), cnt[a[curl]]);
++ cc[cnt[a[curl]]];
++ curl;
}
while (curr > r) {
-- cc[cnt[a[curr]]];
if (cnt[a[curr]] >= sqr) st.erase(p[a[curr]]);
-- cnt[a[curr]];
if (cnt[a[curr]] >= sqr) p[a[curr]] = st.insert(st.end(), cnt[a[curr]]);
++ cc[cnt[a[curr]]];
-- curr;
}
// cal ans[x]
priority_queue<int, vector<int>, greater<int> > nst;
for (list<int>::iterator iter = st.begin(); iter != st.end(); ++ iter) nst.push(* iter);
for (int i = 1; i < sqr; i++) ncnt[i] = cc[i];
for (int i = 1; i < sqr; i++) {
if (ncnt[i]) {
if (2*i < sqr) {
ncnt[2*i] += ncnt[i] / 2;
} else {
int T = ncnt[i] / 2;
while (T--) nst.push(2*i);
}
ans[x] += 2 * i * (ncnt[i] / 2);
ncnt[i] &= 1;
if (ncnt[i]) {
int f = 0;
for (int j = i+1; j < sqr; j++) {
if (ncnt[j]) {
f = j;
break;
}
}
if (!f) nst.push(i);
else {
-- ncnt[f];
ans[x] += i + f;
if (i + f < sqr) ++ ncnt[i + f];
else nst.push(i + f);
}
}
}
}
while (nst.size() >= 2) {
int a = nst.top(); nst.pop();
int b = nst.top(); nst.pop();
ans[x] += a + b;
nst.push(a + b);
}
}
for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
return 0;
}