← 返回题目列表

Codeforces · 2179/H

H. Blackslex 和植物

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

Blackslex 在因紧张的关系、紧张的政治和艰苦的研究而积累的压力中找到了植物和树木的慰藉。

Blackslex 有 $$$n$$$ 植物以直线排列,由植物 $$$1, 2, 3, \ldots n$$$ 组成。最初,每株植物含有 $$$0$$$ 毫升水。

他想要执行 $$$q$$$ 浇水操作,如下所示:

  • 给定每个操作的 $$$l, r$$$
  • 每 $$$l \leq i \leq r$$$ 向第 $$$i$$$ 植物浇水 $$$f(i-l+1)$$$ 毫升水

其中 $$$f(x)$$$ 表示 $$$x$$$ 与 $$$x$$$ 最低有效设置位的值的乘积 $$$^{\text{∗}}$$$ 您的任务是计算出所有浇水操作完成后每个植物中的水量。

$$$^{\text{*}}$$$$$x$$$ 的最低有效设置位的值是 $$$x$$$ 的二进制表示中最右边设置位(为 1 的位)的值。例如,$$$10 = 1010_2$$$ 的最低有效设置位的值为 $$$0010_2 = 2$$$

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$、$$$q$$$ ($$$1 \leq n, q \leq 2\cdot 10^5$$$) - 分别是植物的数量和浇水操作的数量。

每个测试用例的接下来的 $$$q$$$ 行包含两个整数 $$$l$$$、$$$r$$$ ($$$1 \leq l \leq r \leq n$$$) - 每个浇水操作的左边界和右边界。

保证所有测试用例中 $$$n$$$ 的所有值的总和以及 $$$q$$$ 的所有值的总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出 $$$n$$$ 整数,表示每个 $$$i = 1, 2, 3, \ldots, n$$$ 的第 $$$i$$$ 植物中的水量

示例

输入
复制

2
5 3
1 5
2 3
2 5
7 7
1 3
1 6
3 7
4 7
7 7
1 6
5 5

输出
复制

1 6 11 19 21
3 12 10 37 18 43 22

注意

在第一种情况下,每个操作将执行如下:

  1. 第一个操作将:
    • 使用 $$$f(1-1+1) = f(1) = 1$$$ 毫升水浇灌 $$$1$$$-st 植物。
    • 使用 $$$f(2 - 1 + 1) = f(2) = 4$$$ 毫升水给 $$$2$$$-nd 植物浇水。
    • 使用 $$$f(3 - 1 + 1) = f(3) = 3$$$ 毫升水浇灌 $$$3$$$-rd 植物。
    • 使用 $$$f(4 - 1 + 1) = f(4) = 16$$$ 毫升水浇灌第 $$$4$$$ 植物。
    • 使用 $$$f(5 - 1 + 1) = f(5) = 5$$$ 毫升水浇灌第 $$$5$$$ 植物。
  2. 第二个操作将:
    • 使用 $$$f(2 - 2 + 1) = f(1) = 1$$$ 毫升水给 $$$2$$$-nd 植物浇水。
    • 使用 $$$f(3 - 2 + 1) = f(2) = 4$$$ 毫升水浇灌 $$$3$$$-rd 植物。
  3. 第三次操作将:
    • 使用 $$$f(2 - 2 + 1) = f(1) = 1$$$ 毫升水给 $$$2$$$-nd 植物浇水。
    • 使用 $$$f(3 - 2 + 1) = f(2) = 4$$$ 毫升水浇灌 $$$3$$$-rd 植物。
    • 使用 $$$f(4 - 2 + 1) = f(3) = 3$$$ 毫升水给第 $$$4$$$ 植物浇水。
    • 使用 $$$f(5 - 2 + 1) = f(4) = 16$$$ 毫升水给第 $$$5$$$ 植物浇水。

因此,每个植物的总水量为:

  1. $$$1$$$ 毫升
  2. $$$4 + 1 + 1 = 6$$$ 毫升
  3. $$$3 + 4 + 4 = 11$$$ 毫升
  4. $$$16 + 3 = 19$$$ 毫升
  5. $$$5 + 16 = 21$$$ 毫升