「PEOI Rd1」k 叉堆（heap）

Luogu

IDLGP9224

Time2000ms

Memory256MB

DifficultyP5

O2优化

给定一个 $1 \sim n$ 的序列，每个位置 $i$ 有 $k$ 个参数 $a_{i,1},a_{i,2},\dots,a_{i,k}$。已知这个序列是一个按照大根堆的 bfs 序得到的序列。 bfs 序，即按照下图中**红色数字编号的顺序**： ![](https://cdn.luogu.com.cn/upload/image_hosting/73ot5iox.png) 一个大根堆满足条件，当且仅当所有子节点的**所有** $k$ 个权值都小于等于父节点，即 $\forall u\in[1,n],\forall v\in son(u),\forall j \in [1,k],a_{v,j} \leq a_{u,j}$。假设这个大根堆是**完全 $m$ 叉树**，求所有 $m \in [1,n-1]$，使得这个 $m$ 叉堆**满足条件**的 $m$ 的取值。 ## Input 第一行两个整数 $n,k$。接下来 $k$ 行，每行 $n$ 个整数，表示给定的序列。其中，第 $i+1$ 行第 $j$ 列表示的是 $a_{j,i}$。可以理解为，分成 $k$ 行给出了所有位置的 $k$ 个参数。 ## Output 第一行一个整数 $A$，表示所有可能的 $m$ 的取值数量。接下来一行 $A$ 个整数，表示所有的可能的 $m$ 的取值。 [samples] ## Background **数据范围较赛时加强**。 - 2023.04.25：发现 1.50s 时限过于卡常，扩大到 2.00s。 ## Note #### 样例解释样例 $1$ 中，$1,2$ 叉堆显然都符合条件。 --- #### 数据范围 |子任务编号|$n \leq$|分值| |:-:|:-:|:-:| |$1$|$10^3$|$20$| |$2$|$5 \times 10^4$|$20$| |$3$|$2 \times 10^5$|$60$| 对于 $100\%$ 的数据，保证 $1 \leq n \leq 2 \times 10^5$，$1 \leq k \leq 8$，$-10^7 \leq a_{i,j} \leq 10^7$。

Samples

Input #1

3 2
1 1 1
1 1 1

Output #1

2
1 2

Input #2

6 1
2 1 2 1 1 2

Output #2

2
2 5

API Response (JSON)

{
  "problem": {
    "name": "「PEOI Rd1」k 叉堆（heap）",
    "description": {
      "content": "给定一个 $1 \\sim n$ 的序列，每个位置 $i$ 有 $k$ 个参数 $a_{i,1},a_{i,2},\\dots,a_{i,k}$。已知这个序列是一个按照大根堆的 bfs 序得到的序列。 bfs 序，即按照下图中**红色数字编号的顺序**： ![](https://cdn.luogu.com.cn/upload/image_hosting/73ot5iox.png) 一个大根堆满足",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9224"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一个 $1 \\sim n$ 的序列，每个位置 $i$ 有 $k$ 个参数 $a_{i,1},a_{i,2},\\dots,a_{i,k}$。已知这个序列是一个按照大根堆的 bfs 序得到的序列。\n\nbfs 序，即按照下图中**红色数字编号的顺序**：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/73ot5iox.png)\n\n一个大根堆满足...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments