题目详情题解（0）讨论（0）提交记录（0）

CFCF2179H.Blackslex and Plants

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

Blackslex 在因人际关系紧张、政治压力大以及研究压力繁重而积累的压力中，找到了在植物和树木中安慰自己的方式。

Blackslex 拥有 nn 棵依次排成一排的植物，分别为第 1,2,3,…,n1,2,3,\ldots,n 棵。一开始，每棵植物中的水量为 00 毫升。

他打算执行 qq 次浇水操作，具体如下：

  • 对于每次操作，给出 l,rl, r
  • 对于每一棵第 l≤i≤rl \leq i \leq r 棵植物，向其浇灌 f(i−l+1)f(i-l+1) 毫升的水

其中，f(x)f(x) 表示 xx 与 xx 的最低有效位的乘积∗^{\text{∗}}。你的任务是，所有浇水操作结束后，计算每棵植物中的水量。

∗^{\text{∗}} xx 的最低有效位的值指的是 xx 的二进制表示中最右侧为 11 的那一位所表示的值。例如，10=1010210=1010_2 的最低有效位的值为 00102=20010_2=2。

输入格式

第一行包含一个整数 tt（1≤t≤1041 \leq t \leq 10^4）——表示测试用例组数。

每个测试用例的第一行包含两个整数 nn 和 qq（1≤n,q≤2⋅1051 \leq n, q \leq 2\cdot 10^5）——植物数量和浇水操作数量。

每个测试用例接下来的 qq 行，每行包含两个整数 ll 和 rr（1≤l≤r≤n1 \leq l \leq r \leq n）——每次浇水操作的左右区间。

保证所有测试用例的 nn 之和与 qq 之和不超过 2⋅1052\cdot 10^5。

输出格式

对于每个测试用例，输出 nn 个整数，表示每一棵第 ii 棵植物中的水量（i=1,2,...,ni=1,2,...,n）。

输入输出样例

  • 输入#1

    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

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

说明/提示

在第一个样例中，每次操作的细节如下：

  1. 第一次操作：
    • 向第 11 棵植物浇水 f(1−1+1)=f(1)=1f(1-1+1)=f(1)=1 毫升。
    • 向第 22 棵植物浇水 f(2−1+1)=f(2)=4f(2-1+1)=f(2)=4 毫升。
    • 向第 33 棵植物浇水 f(3−1+1)=f(3)=3f(3-1+1)=f(3)=3 毫升。
    • 向第 44 棵植物浇水 f(4−1+1)=f(4)=16f(4-1+1)=f(4)=16 毫升。
    • 向第 55 棵植物浇水 f(5−1+1)=f(5)=5f(5-1+1)=f(5)=5 毫升。
  2. 第二次操作：
    • 向第 22 棵植物浇水 f(2−2+1)=f(1)=1f(2-2+1)=f(1)=1 毫升。
    • 向第 33 棵植物浇水 f(3−2+1)=f(2)=4f(3-2+1)=f(2)=4 毫升。
  3. 第三次操作：
    • 向第 22 棵植物浇水 f(2−2+1)=f(1)=1f(2-2+1)=f(1)=1 毫升。
    • 向第 33 棵植物浇水 f(3−2+1)=f(2)=4f(3-2+1)=f(2)=4 毫升。
    • 向第 44 棵植物浇水 f(4−2+1)=f(3)=3f(4-2+1)=f(3)=3 毫升。
    • 向第 55 棵植物浇水 f(5−2+1)=f(4)=16f(5-2+1)=f(4)=16 毫升。

因此，每棵植物的总水量为：

  1. 11 毫升
  2. 4+1+1=64+1+1=6 毫升
  3. 3+4+4=113+4+4=11 毫升
  4. 16+3=1916+3=19 毫升
  5. 5+16=215+16=21 毫升

由 ChatGPT 5 翻译

首页