题意
对于每个 $k \in \left[1, n\right]$，输出最小的 $m$，满足存在一种将给定的 $n$ 个数划分成 $m$ 段的方案，每段中不同数字的个数不超过 $k$ 个。
题解
做法 1
我一开始想到的就是这个。首先观察到我们一段区间里至少会有 $k$ 个数，因此可以暴力枚举 $k$，然后快速跳。这样是一个调和数。
我们需要对于一个点 $l$，快速找到一个 $r$，使得 $\left[l, r\right]$ 中的不同数个数是 $k + 1$ 个，而 $\left[l, r\right)$ 中的不同数个数是 $k$ 个。二分之后是区间数颜色问题。
区间数不同数个数，我们对于每个 $i$，预处理出 $p_i$，跟 $i$ 颜色相同的在 $i$ 之前的最后一个位置。这样，对于一个查询区间 $\left[l, r\right]$ 来讲，如果 $l \leq i \leq r$ 且 $p_i < l$，那么将颜色加一。
我们可以用主席树或者线段树套 vector 查询。
线段树上二分可以做到 $O\left(n \log^3 n\right)$。主席树上二分可以做到 $O\left(n \log^2 n\right)$。
由于写挂了调不出来，没有代码。
做法 2
根号分治，对于 $k \leq B$，暴力 $O\left(n\right)$ 计算。
对于 $k > B$，不同的答案只有最多 $\frac nB$ 种，答案相同的 $k$ 连续，于是可以对于每个答案二分 $k$ 的区间。
复杂度是 $O\left(Bn + \frac nB n \log n\right)$，取 $B = \sqrt{n \log n}$ 达到最优复杂度 $O\left(n\sqrt{n \log n}\right)$。
代码
/* C++20 is required!
* By Koicy (https://koicy.ly)
* Email n@rbtr.ee
* 我还期待着名为奇迹的魔法，哪怕会凋零会消散只会是一场浮华，我笑纳！
__ __ __ _
_____/ /_ / /_________ ___ / /______ (_)______ __
/ ___/ __ \/ __/ ___/ _ \/ _ \ ______ / //_/ __ \/ / ___/ / / /
/ / / /_/ / /_/ / / __/ __/ /_____/ / ,< / /_/ / / /__/ /_/ /
/_/ /_.___/\__/_/ \___/\___/ /_/|_|\____/_/\___/\__, /
SIGN /___*/
#include <bits/stdc++.h>
#define __NO_MAIN__ false
constexpr bool _MTS = false, SPC_MTS = false;
#define FULL(arg) arg.begin(), arg.end()
// :/
using namespace std;
using tp = long long int;
using vetp = basic_string<tp>;
[[maybe_unused]] constexpr tp ZERO = 0, ONE = 1, INF = -1ull >> 2;
int STRUGGLING(unsigned long long int);
void MIST();
#if !__NO_MAIN__
int main(int argc,char* argv[]){unsigned long long int t=0,_t=1;MIST();if(_MTS&&
!SPC_MTS)cin>>_t;while(t<_t||SPC_MTS){if(STRUGGLING(++t)!=0)return 0;}return 0;}
#endif
template <typename _Ty> class _Lambda_t {_Ty lexp;public:template<typename __Ty>
_Lambda_t(__Ty&&lexp):lexp(static_cast<__Ty&&>(lexp)){}template<typename... __Ty
>decltype(auto)operator()(__Ty&&...args){return lexp(std::ref(*this),static_cast
<__Ty&&>(args)...); } }; template <typename _Ty> decltype(auto) lexp(_Ty&&l_exp)
{ return _Lambda_t<typename std::decay<_Ty>::type>(static_cast<_Ty&&>(l_exp)); }
#ifdef XCODE
#define bg(...){cout<<"["<<__LINE__<<'@'<<++_LT[__LINE__]<<':';BG(__VA_ARGS__);}
size_t _LT[21777]; template<typename _Type>void BG(const _Type&_cur){cout<<' '<<
_cur << ']' << " <<:" << endl; } template<typename _Type,typename... _Other>void
BG(const _Type& _cur, const _Other& ..._other) {cout<< ' '<<_cur;BG(_other...);}
#else
#define bg(...)
#define dputs(...)
#endif
// :/
// :/
int STRUGGLING([[maybe_unused]] unsigned long long int TEST_NUMBER) {
tp n; cin >> n;
vetp a(n + 1, 0);
for (tp i = 1; i <= n; ++i) cin >> a[i];
auto calc = [&](tp k) -> tp {
vetp cnt(n + 1, 0);
tp jmp = 1, f = 0, lst = 1;
for (tp i = 1; i <= n; ++i) {
if (cnt[a[i]] != 0) continue;
cnt[a[i]] = 1;
++f;
if (f > k) {
for (tp j = lst; j < i; ++j) cnt[a[j]] = 0;
lst = i;
++jmp;
f = 1;
}
}
return jmp;
};
tp b = sqrt(n * log2(n));
tp mav = 0, tar = -1;
for (tp k = 1; k <= n; ++k) {
if (k <= b) cout << calc(k) << " \n"[k == n];
else if (k <= mav) cout << tar << " \n"[k == n];
else {
tp v = calc(k);
tp l = k, r = n, tgt = k;
while (l <= r) {
tp mid = (l + r) / 2;
if (calc(mid) < v) r = mid - 1;
else {
l = mid + 1;
tgt = mid;
}
}
cout << v << " \n"[k == n];
mav = tgt;
tar = v;
}
}
return 0;
}
void MIST() {
cin.tie(nullptr)->sync_with_stdio(false);
}
// :\ */