Till I Collapse

题目描述

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.

题意概述

给定一个长度为$n$的数列，第$i$个数为$a_i$。要求将它们分成若干连续段。对于所有$k \in [1, n]$，问至少分成多少段，使得每一段中数字的种类数不超过$k$。

数据范围：$1 \le a_i \le n \le 10^5$。

算法分析 1

有个显然的贪心策略：每一段越长越好。

容易发现答案一定单调不递增。对于$i \le j$，如果$ans_i=ans_j$，那么$ans_i=ans_{i+1}=ans_{i+2}= \cdots =ans_j$。因此我们可以贪心$O(n)$计算出左端点和右端点的$ans$，若它们相等，则将这个区间中的$ans$全都赋成左端点的$ans$；否则，取区间中点，并递归处理左右两个区间。

代码 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

建可持久化线段树，第$i$个节点上的线段树维护区间$[j, i]$中数字的种类数。当遇到一个前面已经出现过的数字时，就在前面出现的位置上减一，在当前位置上加一。枚举$k$，并依据上述贪心策略，即可得到答案。

代码 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;
    return tot;
  }
  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;
  return tot;
}
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;
}