A16815 | $Blackslex and Plants$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

Blackslex 在因人际关系紧张、政治压力大以及研究压力繁重而积累的压力中，找到了在植物和树木中安慰自己的方式。 Blackslex 拥有 $n$ 棵依次排成一排的植物，分别为第 $1,2,3,\ldots,n$ 棵。一开始，每棵植物中的水量为 $0$ 毫升。 他打算执行 $q$ 次浇水操作，具体如下： - 对于每次操作，给出 $l, r$ - 对于每一棵第 $l \leq i \leq r$ 棵植物，向其浇灌 $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$ 棵植物中的水量（$i=1,2,...,n$）。

输入 #1

输出 #1

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

C++ 编辑器

输入

输出