Till I Collapse
题面翻译
将 \(n\) 个数划分成 \(m\) 段使得每中不同数字的个数 \(\le k\)。对于每个 \(k\) 满足 \(1\le k\le n\) 求出最小的 \(m\)。
输入格式
The first line of input contains a single integer \(n\) ( \(1<=n<=10^{5}\) ) — number of Mr. Meeseeks.
The second line contains \(n\) integers \(a_{1},a_{2},...,a_{n}\) separated by spaces ( \(1<=a_{i}<=n\) ) — colors of Mr. Meeseeks in order they standing in a line.
输出格式
In the first and only line of input print \(n\) integers separated by spaces. \(i\) -th integer should be the minimum number of presidios needed if the value of \(k\) is \(i\) .
样例 #1
样例输入 #1
5
1 3 4 3 3
样例输出 #1
4 2 1 1 1
样例 #2
样例输入 #2
8
1 5 7 8 1 7 6 1
样例输出 #2
8 4 3 2 1 1 1 1
提示
For the first sample testcase, some optimal ways of dividing army into squads for each \(k\) are:
- \([1],[3],[4],[3,3]\)
- \([1],[3,4,3,3]\)
- \([1,3,4,3,3]\)
- \([1,3,4,3,3]\)
- \([1,3,4,3,3]\)
For the second testcase, some optimal ways of dividing army into squads for each \(k\) are:
- \([1],[5],[7],[8],[1],[7],[6],[1]\)
- \([1,5],[7,8],[1,7],[6,1]\)
- \([1,5,7],[8],[1,7,6,1]\)
- \([1,5,7,8],[1,7,6,1]\)
- \([1,5,7,8,1,7,6,1]\)
- \([1,5,7,8,1,7,6,1]\)
- \([1,5,7,8,1,7,6,1]\)
- \([1,5,7,8,1,7,6,1]\)
Solution
显然一个贪心的想法是每个选择的区间包含的颜色数量都尽可能多，这样总的段数就会很小。那么当每段区间内的颜色数量为 \(k\) 的时候，显然总的段数会是 \(\le \lfloor\dfrac{n}{k}\rfloor\) 的。这也就意味着枚举每一个颜色段的时间复杂度将会是调和级数的 \(\mathcal O(n\log n)\)。
现在问题转化成为了已知左端点 \(l\)，要求找到一个最大的 \(r\)，使得 \([l,r]\) 间的颜色数量为 \(k\)。如果你不会数区间颜色个数，建议先去试一试 P1972 [SDOI2009] HH的项链。那这道题也可以尝试用主席树来做。
延续那道题的做法，记录一个 \(pre_i\) 表示数字 \(i\) 上一次出现的位置。特殊的，如果数字 \(i\) 没有出现，则定义 \(pre_i=0\)。但是如果继续按照之前的做法，会发现 \(r\) 并不能在主席树上二分解决，如果直接二分找到对应位置的话时间复杂度是 \(\mathcal O(\log^2n)\) 的。所以考虑改变一下主席树的形态。
原来的主席树是建一棵值域线段树，然后按照位置进行可持久化。而这道题为了能够在线段树上二分到 \(r\) 的位置，所以需要建的是普通的维护区间信息的线段树，然后根据值域来进行可持久化。根据那道题的思路，需要查询 \(pre\) 小于 \(l\) 的数量，那么此题就应该按照 \(pre\) 进行可持久化。
那么思路就显而易见了。先建出主席树，查询 \(l\) 对应的 \(r\) 的话就在前 \(l-1\) 棵线段树上查找到最后一个前缀和为 \(k\) 的位置就行了。
代码实现上有一点细节需要注意。
完整代码
#include<bits/stdc++.h>
using namespace std;
namespace Hanx16qwq {
constexpr int _SIZE = 2e5;
int n;
int a[_SIZE + 5], pre[_SIZE + 5], last[_SIZE + 5];
int T[_SIZE + 5];
int ls[(_SIZE << 5) + 5], rs[(_SIZE << 5) + 5];
int sum[(_SIZE << 5) + 5], totNode, tail = 0;
#define mid ((l + r) >> 1)
int Build(int l, int r) {
int cur = ++totNode;
if (l < r)
ls[cur] = Build(l, mid),
rs[cur] = Build(mid + 1, r);
return cur;
}
int Update(int pre, int l, int r, int v) {
int cur = ++totNode;
ls[cur] = ls[pre], rs[cur] = rs[pre], sum[cur] = sum[pre] + 1;
if (l < r) {
if (v <= mid) ls[cur] = Update(ls[pre], l, mid, v);
else rs[cur] = Update(rs[pre], mid + 1, r, v);
}
return cur;
}
pair<int, int> Find(int u, int v, int l, int r, int a, int b, int k) {
if (l > b || r < a || k <= 0) return make_pair(0, 0);
if (l == r) {
return make_pair(l, sum[v] - sum[u]);
}
if (l >= a && r <= b) {
int res = sum[ls[v]] - sum[ls[u]];
if (k <= res) return make_pair(Find(ls[u], ls[v], l, mid, a, b, k).first, sum[v] - sum[u]);
else return make_pair(Find(rs[u], rs[v], mid + 1, r, a, b, k - res).first, sum[v] - sum[u]);
}
auto lres = Find(ls[u], ls[v], l, mid, a, b, k);
auto rres = Find(rs[u], rs[v], mid + 1, r, a, b, k - lres.second);
return make_pair(max(lres.first, rres.first), lres.second + rres.second);
}
int range[_SIZE + 5];
void main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
vector<pair<int, int>> all;
for (int i = 1; i <= n; i++) {
cin >> a[i];
pre[i] = last[a[i]];
last[a[i]] = i;
all.emplace_back(pre[i], i);
}
T[0] = Build(1, n + 1);
sort(all.begin(), all.end());
for (auto it : all) {
++tail;
T[tail] = Update(T[tail - 1], 1, n + 1, it.second);
range[it.first] = max(range[it.first], tail);
}
for (int i = 1; i <= n; i++)
range[i] = max(range[i], range[i - 1]);
for (int k = 1; k <= n; k++) {
int ans = 0;
for (int l = 1; l <= n;) {
int r = Find(T[0], T[range[l - 1]], 1, n + 1, l, n + 1, k + 1).first - 1;
ans++, l = r + 1;
}
cout << ans << ' ';
}
}
}
signed main() {
Hanx16qwq::main();
return 0;
}