## 题目描述

It’s summer vocation now. After tedious milking, cows are tired and wish to take a holiday. So Farmer Carolina considers having a picnic beside the river. But there is a problem, not all the cows consider it’s a good idea! Some cows like to swim in West Lake, some prefer to have a dinner in Shangri-la, and others want to do something different. But in order to manage expediently, Carolina coerces all cows to have a picnic!
Farmer Carolina takes her $N$ cows to the destination, but she finds every cow’s degree of interest in this activity is so different that they all loss their interests. So she has to group them to different teams to make sure that every cow can go to a satisfied team. Considering about the security, she demands that there must be no less than $T$ cows in every team. As every cow has its own interest degree of this picnic, we measure this interest degree’s unit as “Moo~“. Cows in the same team should reduce their Moo~ to the one who has the lowest Moo~ in this team – It’s not a democratical action! So Carolina wishes to minimize the TOTAL reduced Moo~s and groups $N$ cows into several teams.
For example, Carolina has $7$ cows to picnic and their Moo~ are ‘$8 \; 5 \; 6 \; 2 \; 1 \; 7 \; 6$’ and at least $3$ cows in every team. So the best solution is that cow No. $2, 4, 5$ in a team (reduce $((2-1)+(5-1))$ Moo~) and cow No. $1, 3, 6, 7$ in a team (reduce $((7-6)+(8-6))$ Moo~), the answer is $8$.

## 算法分析

$$f_i=\min(f_j+(s_i-s_j)-(i-j)b_j \mid i-j \ge T)$$

\begin{align} f_j+(s_i-s_j)-(i-j)b_j &\le f_k+(s_i-s_k)-(i-k)b_k \\ (f_j-s_j+j \cdot b_j)-(f_k-s_k+k \cdot b_k) &\le i(b_j-b_k) \end{align}
$i$单调递增，因此可以斜率优化。但要注意两点：当$i-j \lt T$时$f_j$不能转移到$f_i$；当$i \lt T$时$f_i$没有意义。

## 代码

/*
* You attempt things that you do not even plan because of your extreme
* stupidity.
*/

#include <algorithm>
#include <cstdio>
#include <cstring>

#define int long long

static int const N = 400005;
int a[N], f[N], s[N], b[N], que[N];

int dety(int i, int j) {
return f[j] - s[j] + b[j] * j - (f[i] - s[i] + b[i] * i);
}

int detx(int i, int j) { return b[j] - b[i]; }

signed main() {
for (int n, k; ~scanf("%lld%lld", &n, &k);) {
for (int i = 1; i <= n; ++i)
scanf("%lld", &a[i]);
std::sort(a + 1, a + n + 1);
for (int i = 1; i <= n; ++i)
s[i] = s[i - 1] + a[i], b[i - 1] = a[i];
int qb = 0, qe = 1;
que[0] = 0;
for (int i = 1; i <= n; ++i) {
for (; qb + 1 < qe &&
dety(que[qb], que[qb + 1]) <= i * detx(que[qb], que[qb + 1]);
++qb)
;
f[i] = f[que[qb]] + s[i] - s[que[qb]] - b[que[qb]] * (i - que[qb]);
if (i - k + 1 >= k) {
for (;
qb + 1 < qe &&
dety(que[qe - 2], que[qe - 1]) * detx(que[qe - 1], i - k + 1) >=
dety(que[qe - 1], i - k + 1) * detx(que[qe - 2], que[qe - 1]);
--qe)
;
que[qe++] = i - k + 1;
}
}
printf("%lld\n", f[n]);
}
return 0;
}


## 题目描述

Teachers of one programming summer school decided to make a surprise for the students by giving them names in the style of the “Hobbit” movie. Each student must get a pseudonym maximally similar to his own name. The pseudonym must be a name of some character of the popular saga and now the teachers are busy matching pseudonyms to student names.
There are $n$ students in a summer school. Teachers chose exactly $n$ pseudonyms for them. Each student must get exactly one pseudonym corresponding to him. Let us determine the relevance of a pseudonym $b$ to a student with name $a$ as the length of the largest common prefix $a$ and $b$. We will represent such value as $LCP(a, b)$. Then we can determine the quality of matching of the pseudonyms to students as a sum of relevances of all pseudonyms to the corresponding students.
Find the matching between students and pseudonyms with the maximum quality.

## 代码

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>

int min(int a, int b) {
return a < b ? a : b;
}

static const int N = 800005;
int numn = 1, tot;
char s[N];
struct Trie {
int child[26];
std :: vector <int> rec[2];
} node[N];
std :: vector <std :: pair <int, int> > ans;

void insert(char s[], int id, int val) {
int len = strlen(s), root = 0;
for (int i = 0; i < len; ++ i) {
if (! node[root].child[s[i] - 'a']) node[root].child[s[i] - 'a'] = numn ++;
root = node[root].child[s[i] - 'a'];
}
node[root].rec[val].push_back(id);
}

void merge(std :: vector <int> &a, std :: vector <int> &b) {
if (a.size() < b.size()) swap(a, b);
a.insert(a.end(), b.begin(), b.end());
}

void dfs(int t, int dep) {
for (int i = 0; i < 26; ++ i)
if (node[t].child[i]) {
dfs(node[t].child[i], dep + 1);
merge(node[t].rec[0], node[node[t].child[i]].rec[0]);
merge(node[t].rec[1], node[node[t].child[i]].rec[1]);
}
while (! node[t].rec[0].empty() && ! node[t].rec[1].empty()) {
tot += dep;
ans.push_back(std :: make_pair(node[t].rec[0][node[t].rec[0].size() - 1], node[t].rec[1][node[t].rec[1].size() - 1]));
node[t].rec[0].pop_back(), node[t].rec[1].pop_back();
}
}

int main() {
int n; scanf("%d", &n);
for (int i = 0; i < n; ++ i) scanf(" %s", s), insert(s, i + 1, 0);
for (int i = 0; i < n; ++ i) scanf(" %s", s), insert(s, i + 1, 1);
dfs(0, 0);
printf("%d\n", tot);
for (int i = 0; i < n; ++ i) printf("%d %d\n", ans[i].first, ans[i].second);
return 0;
}


## 题目描述

$N$ friends gathered in order to play chess, according to the following rules. In the first game, two of the $N$ friends will play. In the second game, the winner of the first game will play against another friend (maybe even the same friend who lost the first game). In the third game, the winner of the second game will play against someone else and so on.. No game will end as a draw (tie). Given the number of games each of the $N$ friends played, find a schedule for the games, so that the above rules are obeyed.

## 代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct IOManager {
template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); }
inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; }
inline int read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); }
template <typename T> inline IOManager operator > (T &x) { read(x); return *this; }
template <typename T> inline void write(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + '0'); }
inline void write(char c) { putchar(c); }
inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); }
template <typename T> inline IOManager operator < (T x) { write(x); return *this; }
} io;

struct Solver {
private:
static const int N = 110;
int n, sum;
pair <int, int> a[N];
vector <pair <int, int> > ans;
void input() {
io > n;
for (int i = 1; i <= n; ++ i) io > a[i].first, a[i].second = i, sum += a[i].first;
}
void process() {
io < sum >> 1 < '\n';
sort(a + 1, a + n + 1, greater <pair <int, int> >());
int p = 1;
for (int i = 0; i < sum >> 1; ++ i) {
if (a[p].first == 1) ans.push_back(make_pair(a[p + 1].second, a[p].second)), -- a[p].first, -- a[++ p].first;
else ans.push_back(make_pair(a[p].second, 0)), -- a[p].first;
}
for (int i = 0; i < sum >> 1; ++ i)
if (! ans[i].second)
for (int j = 1; j <= n; ++ j) if (a[j].first && a[j].second != ans[i].first) { ans[i].second = a[j].second, -- a[j].first; break; }
for (int i = 0; i < sum >> 1; ++ i) io < ans[i].first < ' ' < ans[i].second < '\n';
}

public:
void solve() { input(), process(); }
} solver;

int main() {
solver.solve();
return 0;
}


## 题目描述

You are given a connected weighted graph with $n$ vertices and $m$ edges. The graph doesn’t contain loops nor multiple edges. Consider some edge with id $i$. Let’s determine for this edge the maximum integer weight we can give to it so that it is contained in all minimum spanning trees of the graph if we don’t change the other weights.
You are to determine this maximum weight described above for each edge. You should calculate the answer for each edge independently, it means there can’t be two edges with changed weights at the same time.

## 代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
struct line {
long long u, v, c, id; bool mst;
bool operator < (const line &a) const { return c < a.c; }
} l[200001];
struct edge {
long long v, c, id, nxt;
} e[400001];
long long n, m, nume, h[200001], fa[200001], ans[200001];
long long depth[200001], up[200001][20], ma[200001][20], uid[200001];
long long get_fa(long long t) { return t == fa[t] ? t : fa[t] = get_fa(fa[t]); }
void add_edge(long long u, long long v, long long c, long long id) {
e[++nume].v = v, e[nume].c = c, e[nume].id = id, e[nume].nxt = h[u], h[u] = nume;
e[++nume].v = u, e[nume].c = c, e[nume].id = id, e[nume].nxt = h[v], h[v] = nume;
}
void dfs(long long t, long long fa) {
for (int i = h[t]; i; i = e[i].nxt)
if (e[i].v != fa) {
depth[e[i].v] = depth[t] + 1, up[e[i].v][0] = t;
ma[e[i].v][0] = e[i].c, uid[e[i].v] = e[i].id, dfs(e[i].v, t);
}
}
long long get_max(long long u, long long v) {
long long ret = 0;
if (depth[u] < depth[v]) u ^= v ^= u ^= v;
for (int i = 19; i >= 0; --i)
if (depth[u] - depth[v] >= (1 << i))
ret = max(ret, ma[u][i]), u = up[u][i];
if (u == v) return ret;
for (int i = 19; i >= 0; --i)
if (up[u][i] != up[v][i])
ret = max(ret, max(ma[u][i], ma[v][i])), u = up[u][i], v = up[v][i];
return max(ret, max(ma[u][0], ma[v][0]));
}
void update(long long u, long long v, long long val) {
if (depth[u] < depth[v]) u ^= v ^= u ^= v;
long long p = u, q = v;
for (int i = 19; i >= 0; --i)
if (depth[p] - depth[q] >= (1 << i)) p = up[p][i];
if (p != q) {
for (int i = 19; i >= 0; --i)
if (up[p][i] != up[q][i]) p = up[p][i], q = up[q][i];
p = up[p][0];
}
u = get_fa(u), v = get_fa(v);
while (depth[u] > depth[p])
ans[uid[u]] = val - 1, q = get_fa(up[u][0]), fa[u] = q, u = get_fa(u);
while (depth[v] > depth[p])
ans[uid[v]] = val - 1, q = get_fa(up[v][0]), fa[v] = q, v = get_fa(v);
}
int main()
{
cin >> n >> m, memset(ans, -1, sizeof ans);
if (n == m + 1) {
for (int i = 1; i <= m; cout << -1 << ' ', ++i); cout << endl; return 0;
}
for (int i = 1; i <= n; fa[i] = i, ++i);
for (int i = 1; i <= m; cin >> l[i].u >> l[i].v >> l[i].c, l[i].id = i, ++i);
sort(l + 1, l + m + 1);
for (int i = 1; i <= m; ++i) {
long long u = get_fa(l[i].u), v = get_fa(l[i].v);
if (u != v) add_edge(l[i].u, l[i].v, l[i].c, l[i].id), fa[u] = v, l[i].mst = true;
}
depth[1] = 1, dfs(1, 0);
for (int i = 1; i < 20; ++i)
for (int j = 1; j <= n; ++j) {
up[j][i] = up[up[j][i - 1]][i - 1];
ma[j][i] = max(ma[j][i - 1], ma[up[j][i - 1]][i - 1]);
}
for (int i = 1; i <= n; fa[i] = i, ++i);
for (int i = 1; i <= m; ++i)
if (!l[i].mst) {
ans[l[i].id] = get_max(l[i].u, l[i].v) - 1;
update(l[i].u, l[i].v, l[i].c);
}
for (int i = 1; i <= m; cout << ans[i] << ' ', ++i);
cout << endl;
return 0;
}


## 题目描述

As we know, DZY loves playing games. One day DZY decided to play with a $n \times m$ matrix. To be more precise, he decided to modify the matrix with exactly $k$ operations.
Each modification is one of the following:

• Pick some row of the matrix and decrease each element of the row by $p$. This operation brings to DZY the value of pleasure equal to the sum of elements of the row before the decreasing.
• Pick some column of the matrix and decrease each element of the column by $p$. This operation brings to DZY the value of pleasure equal to the sum of elements of the column before the decreasing.

DZY wants to know: what is the largest total value of pleasure he could get after performing exactly $k$ modifications? Please, help him to calculate this value.

## 代码

#include <iostream>
#include <queue>
using namespace std;
priority_queue<long long> r, c;
long long n, m, k, p, s, t, ans = -1e18, a[1001][1001], rr[1000001], cc[1000001];
int main()
{
cin >> n >> m >> k >> p;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) cin >> a[i][j];
for (int i = 1; i <= n; ++i) {
long long s = 0;
for (int j = 1; j <= m; ++j) s += a[i][j];
r.push(s);
}
for (int j = 1; j <= m; ++j) {
long long s = 0;
for (int i = 1; i <= n; ++i) s += a[i][j];
c.push(s);
}
for (int i = 1; i <= k; ++i) {
long long u = r.top(); r.pop();
rr[i] = rr[i - 1] + u;
r.push(u - p * m);
u = c.top(); c.pop();
cc[i] = cc[i - 1] + u;
c.push(u - p * n);
}
for (int i = 0; i <= k; ++i) ans = max(ans, rr[i] + cc[k - i] - p * i * (k - i));
cout << ans << endl;
return 0;
}


## 题目描述

Lesha plays the recently published new version of the legendary game hacknet. In this version character skill mechanism was introduced. Now, each player character has exactly $n$ skills. Each skill is represented by a non-negative integer $a_i$ — the current skill level. All skills have the same maximum level $A$.
Along with the skills, global ranking of all players was added. Players are ranked according to the so-called Force. The Force of a player is the sum of the following values:

• The number of skills that a character has perfected (i.e., such that $a_i=A$), multiplied by coefficient $c_f$.
• The minimum skill level among all skills ($\min(a_i)$), multiplied by coefficient $c_m$.

Now Lesha has m hacknetian currency units, which he is willing to spend. Each currency unit can increase the current level of any skill by $1$ (if it’s not equal to $A$ yet). Help him spend his money in order to achieve the maximum possible value of the Force.

## 代码

#include <iostream>
#include <algorithm>
using namespace std;
struct skill {
long long a, id;
} s[100002];
bool cmp1(skill a, skill b) { return a.a < b.a; }
bool cmp2(skill a, skill b) { return a.id < b.id; }
long long n, A, cf, cm, m, ans, pnt, cnt, rec[3], pre[100002], suf[100002];
int main()
{
cin >> n >> A >> cf >> cm >> m;
for (int i = 1; i <= n; ++i) {
cin >> s[i].a; s[i].id = i;
}
sort(s + 1, s + n + 1, cmp1);
for (int i = 1; i <= n; ++i) pre[i] = pre[i - 1] + s[i].a;
for (int i = n; i; --i) suf[i] = suf[i + 1] + s[i].a;
cnt = 0, pnt = n, rec[0] = n + 1;
while (pnt > 0 && (n - pnt + 1) * A - suf[pnt] <= m) --pnt;
for (++pnt; pnt <= n + 1; ++pnt) {
long long rem = m - (n - pnt + 1) * A + suf[pnt];
while (cnt < pnt && s[cnt].a * cnt - pre[cnt] <= rem) ++cnt; --cnt;
if (cnt) (rem -= s[cnt].a * cnt - pre[cnt]) /= cnt; else rem = 1e18;
if (ans < (n - pnt + 1) * cf + min((s[cnt].a + rem), A) * cm) {
ans = (n - pnt + 1) * cf + min((s[cnt].a + rem), A) * cm;
rec[0] = pnt, rec[1] = cnt, rec[2] = min((s[cnt].a + rem), A);
}
}
for (int i = 1; i <= rec[1]; ++i) s[i].a = rec[2];
for (int i = rec[0]; i <= n; ++i) s[i].a = A;
sort(s + 1, s + n + 1, cmp2);
cout << ans << endl;
for (int i = 1; i <= n; ++i) cout << s[i].a << ' ';
cout << endl;
return 0;
}


## 题目描述

There are $n$ people and $k$ keys on a straight line. Every person wants to get to the office which is located on the line as well. To do that, he needs to reach some point with a key, take the key and then go to the office. Once a key is taken by somebody, it couldn’t be taken by anybody else.
You are to determine the minimum time needed for all $n$ people to get to the office with keys. Assume that people move a unit distance per $1$ second. If two people reach a key at the same time, only one of them can take the key. A person can pass through a point with a key without taking it.

## 代码1

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int n, k, p, ans = 2e9, a[1001], b[2001];
int get_dist(int x, int y) { return abs(a[x] - b[y]) + abs(b[y] - p); }
int main()
{
cin >> n >> k >> p;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= k; ++i) cin >> b[i];
sort(a + 1, a + n + 1), sort(b + 1, b + k + 1);
for (int i = 1; i <= k - n + 1; ++i) {
int ma = 0;
for (int j = i; j <= i + n - 1; ++j) ma = max(ma, get_dist(j - i + 1, j));
ans = min(ans, ma);
}
cout << ans << endl;
return 0;
}


## 代码2

#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
int n, k, p, a[1001], b[2001], f[1001][2001];
int get_dist(int x, int y) { return abs(a[x] - b[y]) + abs(b[y] - p); }
int main()
{
cin >> n >> k >> p; memset(f, 0x7f, sizeof(f));
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= k; ++i) cin >> b[i];
sort(a + 1, a + n + 1), sort(b + 1, b + k + 1);
for (int i = 0; i <= k; ++i) f[0][i] = 0;
for (int i = 1; i <= n; ++i)
for (int j = i; j <= k; ++j)
f[i][j] = min(f[i][j - 1], max(f[i - 1][j - 1], get_dist(i, j)));
cout << f[n][k] << endl;
return 0;
}


## 题目描述

Arkady needs your help again! This time he decided to build his own high-speed Internet exchange point. It should consist of $n$ nodes connected with minimum possible number of wires into one network (a wire directly connects two nodes). Exactly $k$ of the nodes should be exit-nodes, that means that each of them should be connected to exactly one other node of the network, while all other nodes should be connected to at least two nodes in order to increase the system stability.
Arkady wants to make the system as fast as possible, so he wants to minimize the maximum distance between two exit-nodes. The distance between two nodes is the number of wires a package needs to go through between those two nodes.
Help Arkady to find such a way to build the network that the distance between the two most distant exit-nodes is as small as possible.

## 代码

#include <cstdio>
#include <queue>
using namespace std;
struct edge {
int v, nxt;
} e[400001];
int n, m, nume, h[200001], depth[200001];
queue<int> que;
void add_edge(int u, int v) {
e[++nume].v = v, e[nume].nxt = h[u], h[u] = nume;
}
int main()
{
scanf("%d%d", &n, &m);;
for (int i = 1; i <= m; ++i) {
add_edge(1, i + 1), depth[i + 1] = 1;
que.push(i + 1);
}
for (int i = m + 2; i <= n; ++i) {
int u = que.front(); que.pop();
add_edge(u, i), depth[i] = depth[u] + 1;
que.push(i);
}
printf("%d\n", depth[n] + depth[n - 1]);
for (int i = 1; i <= n; ++i) {
for (int j = h[i]; j; j = e[j].nxt) {
printf("%d %d\n", i, e[j].v);
}
}
return 0;
}


## 题目描述

Chef has a calculator which has two screens and two buttons. Initially, each screen shows the number zero. Pressing the first button increments the number on the first screen by $1$, and each click of the first button consumes $1$ unit of energy.
Pressing the second button increases the number on the second screen by the number which is currently appearing on the first screen. Each click of the second button consumes $B$ units of energy.
Initially the calculator has $N$ units of energy.
Now chef wonders what the maximum possible number is, that he gets on the second screen of the calculator, with the limited energy.

## 代码

#include <iostream>
#include <cmath>
using namespace std;
long long T, n, b, p, q, x, ans;
long double k;
int main()
{
cin >> T;
while (T--) {
cin >> n >> b;
ans = 0;
k = 1.0 * n / 2 / b;
p = floor(k), q = ceil(k);
x = n - b * p;
if (x > 0 && x < n) ans = max(ans, p * x);
x = n - b * q;
if (x > 0 && x < n) ans = max(ans, q * x);
cout << ans << endl;
}
return 0;
}


## 题目描述

Rick and Morty want to find MR. PBH and they can’t do it alone. So they need of Mr. Meeseeks. They Have generated $n$ Mr. Meeseeks, standing in a line numbered from $1$ to $n$. Each of them has his own color. $i$-th Mr. Meeseeks’ color is $a_i$.
Rick and Morty are gathering their army and they want to divide Mr. Meeseeks into some squads. They don’t want their squads to be too colorful, so each squad should have Mr. Meeseeks of at most $k$ different colors. Also each squad should be a continuous subarray of Mr. Meeseeks in the line. Meaning that for each $1 \le i \le e \le j \le n$, if Mr. Meeseeks number $i$ and Mr. Meeseeks number $j$ are in the same squad then Mr. Meeseeks number $e$ should be in that same squad.
Also, each squad needs its own presidio, and building a presidio needs money, so they want the total number of squads to be minimized.
Rick and Morty haven’t finalized the exact value of $k$, so in order to choose it, for each $k$ between $1$ and $n$ (inclusive) need to know the minimum number of presidios needed.

## 代码1

#include <cstdio>
#include <cstring>
using namespace std;
int n, last, a[100001], c[100001], ans[100001];
int get(int t) {
memset(c, 0, sizeof(c));
int p = 0, q = 1, ret = 0;
while (q <= n) {
int cnt = 1; c[a[q]] = 1;
while (q < n) {
if (cnt < t || c[a[q + 1]]) {
cnt += !c[a[++q]], ++c[a[q]];
} else break;
}
while (p < q) --c[a[++p]];
++q, ++ret;
}
return ret;
}
void solve(int l, int r) {
if (l > r) return;
ans[l] = get(l), ans[r] = get(r);
if (ans[l] == ans[r]) {
for (int i = l + 1; i < r; ++i) ans[i] = ans[l];
return;
}
int mid = l + r >> 1;
solve(l + 1, mid), solve(mid + 1, r - 1);
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
solve(1, n);
for (int i = 1; i <= n; ++i) printf("%d ", ans[i]);
printf("\n");
return 0;
}


## 代码2

#include <cstdio>
using namespace std;
struct node_type {
int val, child[2];
} node[4000001];
int n, tot, ans, a[100001], root[100001], pre[100001];
int insert_line(int root, int l, int r, int p, int val) {
if (l == r) {
node[++tot].val = node[root].val + val;
node[tot].child[0] = node[tot].child[1] = 0;
}
int mid = l + r >> 1, ch;
if (p <= mid) {
ch = insert_line(node[root].child[0], l, mid, p, val);
node[++tot].child[0] = ch, node[tot].child[1] = node[root].child[1];
} else {
ch = insert_line(node[root].child[1], mid + 1, r, p, val);
node[++tot].child[0] = node[root].child[0], node[tot].child[1] = ch;
}
node[tot].val = node[node[tot].child[0]].val + node[node[tot].child[1]].val;
}
int query(int root, int l, int r, int p) {
if (l == r) if (p >= node[root].val) return l; else return l + 1;
int mid = l + r >> 1;
if (p >= node[node[root].child[1]].val) return query(node[root].child[0], l, mid, p - node[node[root].child[1]].val);
else return query(node[root].child[1], mid + 1, r, p);
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
pre[a[1]] = 1, root[1] = insert_line(0, 1, n, 1, 1);
for (int i = 2; i <= n; ++i) {
int rt = root[i - 1];
if (pre[a[i]]) rt = insert_line(rt, 1, n, pre[a[i]], -1);
pre[a[i]] = i, root[i] = insert_line(rt, 1, n, i, 1);
}
for (int i = 1; i <= n; ++i) {
if (ans != 1) {
ans = 0;
int l = n, r;
while (l) r = l, l = query(root[r], 1, n, i) - 1, ++ans;
}
printf("%d ", ans);
}
printf("\n");
return 0;
}