CF786C Till I Collapse()

Till I Collapse

Luogu CF786C

Codeforces 786C

题面翻译

将 \(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;
}
————————

Till I Collapse

Luogu CF786C

Codeforces 786C

题面翻译

将 \(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;
}