Cut and Stick
Created by LXC on Tue Jul 18 10:04:41 2023
https://codeforces.com/problemset/problem/1514/D
ranting: 2000
tag: binary search, data structures, greedy, implementation, sortings
problem
给出一个数组，以及q次查询，每次查询一个区间，问最少可以将这个区间分成多少个子序列，使得每个子序列出现最多的数不超过数组长度的一半（长度为奇数则向上取整）。若f为区间最大频次，len为区间长度，$f \le \lceil \frac{len}{f} \rceil$
solution
关键结论：划分的子序列个数是max(1, f-(len-f))
所以我们需要较快求出区间的最大频次。
注意到可以离线，所以可以用莫队。时间复杂度$O(n\sqrt n)$
另一种思路就是随机思想，由于只有最大频次大于区间一半才能需要分成多个子序列。假设最大频次大于区间一半，我们随机选取一个区间内的数，其不属于最大频次的数的概率小于$\frac{1}{2}$，我们选取n次，n次每个都不属于最大频次的数的概率是小于$\frac{1}{2^n}$的。
而我们选取个30次，几乎不可能选不到最大频次的数。
对于每次抽到的数，我们需要求其在区间内的频次，我们可以预处理每个数的前缀和。然后两次二分可以得到区间内的出现次数。
code
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
| #include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define N 1000006
#define MOD 998244353
using namespace std;
int bsz;
int feq[N], cnt[N], v[N], ans[N];
int mxf = 0;
struct Node {
int l, r, id;
bool operator<(Node& o) {
return l / bsz == o.l / bsz ? r < o.r : l / bsz < o.l / bsz;
}
} a[N];
void add(int x) {
cnt[feq[v[x]]]--;
feq[v[x]]++;
cnt[feq[v[x]]]++;
mxf = max(mxf, feq[v[x]]);
}
void sub(int x) {
cnt[feq[v[x]]]--;
feq[v[x]]--;
cnt[feq[v[x]]]++;
if (mxf == feq[v[x]] + 1 && cnt[feq[v[x]] + 1] == 0)
mxf = feq[v[x]];
}
void sol() {
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> v[i];
}
for (int i = 0; i < q; i++) {
cin >> a[i].l >> a[i].r;
a[i].id = i;
}
bsz = sqrt(n);
sort(a, a + q);
int l = 1, r = 0;
for (int i = 0; i < q; i++) {
while (a[i].l < l)
add(--l);
while (a[i].r > r)
add(++r);
while (a[i].l > l)
sub(l++);
while (a[i].r < r)
sub(r--);
ans[a[i].id] = max(1, 2 * mxf - (r - l + 1));
}
for (int i = 0; i < q; i++) {
cout << ans[i] << "\n";
}
}
void sol2() {
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, q;
cin >> n >> q;
vector<int> a(n);
vector<vector<int>> g(n + 1);
for (int i = 0; i < n; i++) {
cin >> a[i];
g[a[i]].push_back(i);
}
while (q--) {
int l, r;
cin >> l >> r;
l--;
r--;
int feq = 0;
for (int i = 0; i < 40; i++) {
int sl = a[uniform_int_distribution<int>(l, r)(rng)];
int x = lower_bound(g[sl].begin(), g[sl].end(), l) - g[sl].begin();
int y = upper_bound(g[sl].begin(), g[sl].end(), r) - g[sl].begin();
feq = max(feq, y - x);
}
cout << max(1, 2 * feq - (r - l + 1)) << "\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#ifndef SINGLE_INPUT
int t;
cin >> t;
while (t--) {
sol();
}
#else
sol();
#endif
return 0;
}
|