HILO

题目描述

Bessie 知道一个数 $x+0.5$，其中 $x$ 是介于 $0$ 到 $N$（含端点）之间的某个整数（$1\le N\le 2 \cdot 10^5$）。 Elsie 正在尝试猜出这个数。她可以提出形如“$i$ 高还是低？”的问题，其中 $i$ 是介于 $1$ 到 $N$（含端点）之间的整数。Bessie 的回答规则是：如果 $i$ 大于 $x+0.5$，则回答 "HI"；如果 $i$ 小于 $x+0.5$，则回答 "LO"。

Elsie 想出了如下策略来猜 Bessie 的数。在开始任何猜测之前，她先生成一个包含 $N$ 个数的列表，其中从 $1$ 到 $N$ 的每个数恰好出现一次（换句话说，该列表是一个长度为 $N$ 的排列）。然后她按照列表中的顺序依次猜测其中出现的数字。

不过，Elsie 会跳过任何不必要的猜测。也就是说：如果 Elsie 即将猜某个数字 $i$，并且她之前猜过某个 $j<i$ 且 Bessie 回答了 "HI"，那么 Elsie 将不会猜 $i$，而是继续列表中的下一个数字。类似地，如果她即将猜某个数字 $i$，并且她之前猜过某个 $j>i$ 且 Bessie 回答了 "LO"，那么 Elsie 将不会猜 $i$，而是继续列表中的下一个数字。可以证明，使用该策略，无论她生成的排列是什么，Elsie 总能唯一确定 $x$。

如果我们把 Bessie 的所有回答（"HI" 或 "LO"）按顺序拼接成一个字符串 $S$，那么 Bessie 说出 "HILO" 的次数等于 $S$ 中长度为 $4$ 且等于 "HILO" 的子串个数。

Bessie 知道 Elsie 会使用该策略；此外，她也知道 Elsie 将使用的具体排列。然而，Bessie 尚未决定要选择哪个 $x$。

请帮助 Bessie 对每个 $x$ 求出她会说出 "HILO" 的次数。

输入格式

第一行包含 $N$。 第二行包含 Elsie 的长度为 $N$ 的排列。

输出格式

对每个 $x$ 从 $0$ 到 $N$（含端点），输出 Bessie 说出 HILO 的次数，每个结果占一行。

5
5 1 2 4 3

0
1
1
2
1
0

提示

对于 $x=0$，Bessie 将说 "HIHI"，因此 "HILO" 的总次数为 $0$。 对于 $x=2$，Bessie 将说 "HILOLOHIHI"，因此 "HILO" 的总次数为 $1$。 对于 $x=3$，Bessie 将说 "HILOLOHILO"，因此 "HILO" 的总次数为 $2$。

评分： 测试点 1 到 4 满足 $N \leq 5000$。 测试点 5 到 8 的排列是均匀随机排列。 测试点 9 到 20 没有额外限制。 题目致谢：Richard Qi

标签: USACO|2021|Gold

来源

USACO|2021|Gold