# CF786C Till I Collapse()-其他

## CF786C Till I Collapse()

Luogu CF786C

Codeforces 786C

### 输入格式

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$$ .

5
1 3 4 3 3

4 2 1 1 1

8
1 5 7 8 1 7 6 1

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

#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;
}
————————

Luogu CF786C

Codeforces 786C

### 输入格式

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$$ .

5
1 3 4 3 3

4 2 1 1 1

8
1 5 7 8 1 7 6 1

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

#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;
}