「题解」P9224 k 叉堆

AtomAlpaca

题意
题解
代码

题意

题解

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

首先考虑 $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); } }
}

Table of contents

题意

题解

代码