「题解」P9224 k 叉堆

AtomAlpaca · 2023-10-26 10:30:23 · 题解

题意

link

题解

提供一个不需要根号分治的做法。

首先考虑 k 叉堆的情况下，每个点的儿子的区间。考虑这样构造 k 叉堆：维护一个没被成为儿子的节点队列，从小到大考虑每个点，将队列中前 k 个树拎出来成为它的儿子。

那么对于节点 n，它前面有 (n - 1)\times k 个节点被分配了，而 1 节点不能被分配为其它节点的儿子，所以节点 n 的儿子区间是 [k(x - 1) + 2, kx + 1] 这一段。于是我们考虑对每一维信息维护一个 st 表，从小到大枚举叉数，检查每个节点的儿子区间内是否有比自己大的就可以了。

复杂度是 O(k(\sum_{i=1}^{n-1}{\frac{n}{i}})) = O(knH_n)，其中 H 是调和数。考虑到调和数增长很慢，几乎是 \log 级别的，这个做法应该是比出题人题解更优的。

代码

#include <bits/stdc++.h>

const int MAX = 2e5 + 5;

int n, k;
int a[MAX], st[21][MAX];
std::bitset <MAX> ans;

int mx(int l, int r)
{
  r = std::min(r, n); int lg = log2(r - l + 1);
  return std::max(st[lg][l], st[lg][r - (1 << lg) + 1]);
}

void solve()
{
  for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); st[0][i] = a[i]; }
  for (int i = 1; (1 << i) <= n; ++i)
  {
    for (int j = 1; j + (1 << i) - 1 <= n; ++j)
    {
      st[i][j] = std::max(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
    }
  }
  for (int k = 1; k < n; ++k)
  {
    if (!ans[k]) { continue; }
    for (int i = 1; k * (i - 1) + 2 <= n; ++i)
    {
      if (mx(k * (i - 1) + 2, k * i + 1) > a[i]) { ans[k] = false; break; }
    }
  }
}

int main()
{
  scanf("%d%d", &n, &k);
  for (int i = 1; i <  n; ++i) { ans[i] = true; }
  for (int i = 1; i <= k; ++i) { solve(); }
  printf("%ld\n", ans.count());
  for (int i = 1; i <  n; ++i) { if (ans[i]) { printf("%d ", i); } }
}