← 返回题目列表

Codeforces · 2203/F

F. 一次交换的二分查找

中文机器翻译题面 查看原题

考虑以下算法,用于在长度为 $$$n$$$ 的数组 $$$a$$$ 中搜索整数 $$$x$$$,其中元素编号从 $$$1$$$ 到 $$$n$$$:

  1. 初始化 $$$l = 1$$$ 和 $$$r = n$$$;
  2. 如果$$$l \gt r$$$,则终止算法并报告未找到所需元素;
  3. 计算 $$$m = \lfloor \frac{l + r}{2} \rfloor$$$;
  4. 如果$$$a_m = x$$$,则终止算法并报告找到所需元素;
  5. 如果$$$a_m \lt x$$$,则设置$$$l = m + 1$$$,否则设置$$$r = m - 1$$$;
  6. 转到步骤 $$$2$$$。

可以看出,如果数组$$$a$$$按非降序排序,则该算法将成功找到$$$a$$$中的任何元素。

你的任务如下:对于给定的数字$$$n$$$,考虑所有对$$$(i, j)$$$,使得$$$1 \le i \lt j \le n$$$。对于每一对,您需要计算其 美女 长度为 $$$m$$$(其中 $$$m \ge 2$$$)的数组 $$$b$$$ 的 — 如果我们采用数组 $$$a = [1, 2, 3, \dots, n]$$$ 并交换元素 $$$a_i$$$ 和 $$$a_j$$$ ,则通过所描述的算法可以成功找到的整数 $$$x$$$ 的数量。之后,对于从 $$$0$$$ 到 $$$n$$$ 的每个 $$$k$$$,您需要输出 $$$p_k$$$ — 与美丽 $$$k$$$ 配对的数量。

输入

输入的唯一一行包含一个整数 $$$n$$$ ($$$3 \le n \le 5 \cdot 10^6$$$)。

输出

打印 $$$n+1$$$ 整数 $$$p_0, p_1, \dots, p_n$$$,其中 $$$p_k$$$ 是 $$$(i, j)$$$ 与美丽 $$$k$$$ 的对数。

示例

输入
复制

4

输出
复制

0 0 3 3 0 

输入
复制

5

输出
复制

0 0 2 4 4 0 

输入
复制

3

输出
复制

0 1 2 0 

输入
复制

13

输出
复制

0 0 0 0 0 0 1 3 8 9 21 24 12 0 

注意

考虑一个 $$$n = 4$$$ 的示例:

  • 如果我们交换$$$a_1$$$和$$$a_2$$$,则可以成功找到$$$1$$$、$$$3$$$和$$$4$$$;
  • 如果我们交换$$$a_1$$$和$$$a_3$$$,则可以成功找到$$$2$$$和$$$4$$$;
  • 如果我们交换$$$a_2$$$和$$$a_3$$$,则可以成功找到$$$1$$$、$$$3$$$和$$$4$$$;
  • 如果我们交换$$$a_1$$$和$$$a_4$$$,则可以成功找到$$$2$$$和$$$3$$$;
  • 如果我们交换$$$a_2$$$和$$$a_4$$$,则可以成功找到$$$1$$$和$$$4$$$;
  • 如果我们交换$$$a_3$$$和$$$a_4$$$,则可以成功找到$$$1$$$、$$$2$$$和$$$4$$$。