自动搬运

查看原文

来自洛谷，原作者为

	AtomAlpaca 厌见桃株，夜来悲哭。生世徒劳，风吹烛。

搬运于2025-08-24 22:46:31，当前版本为作者最后更新于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); } }
}