资讯详情

H. Blackslex and Plants

Blackslex has found solace in plants and trees amidst accumulated stress from strained relationships, stressful politics, and strenuous research.

Blackslex has $n$ plants ordered in a straight line, consisting of plant $1, 2, 3, \ldots n$. Initially, every plant contains $0$ millilitres of water.

He wants to perform $q$ watering operations as follows :

• Given $l, r$ for each operation
• water $f(i-l+1)$ millilitres of water onto the $i$-th plant for every $l \leq i \leq r$

where $f(x)$ denotes the product of $x$ and the value of the least significant set bit of $x$ $^{\text{∗}}$ Your task is to figure out the amount of water in each plant after all watering operations are done.

$^{\text{∗}}$The value of the least significant set bit of $x$ is the value of the rightmost set bit (bit that is 1) in the binary representation of $x$. For instance, the value of the least significant set bit of $10 = 1010_2$ is $0010_2 = 2$

Input

The first line contains an integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

The first line of each test case contains two integers $n$, $q$ ($1 \leq n, q \leq 2\cdot 10^5$) — the number of plants and the number of watering operations, respectively.

The next $q$ lines of each test case contain two integers $l$, $r$ ($1 \leq l \leq r \leq n$) — the left bound and the right bound for each watering operation.

It is guaranteed that the sum of all values of $n$ and the sum of all values of $q$ across all test cases do not exceed $2 \cdot 10^5$.

Output

For each test case, output $n$ integers representing the amount of water in the $i$-th plant for each $i = 1, 2, 3, \ldots, n$

Example

Input

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

Output

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

Note

In the first case, each operation will be performed as follows :

1. The first operation will :
   • water the $1$-st plant using $f(1-1+1) = f(1) = 1$ millilitres of water.
   • water the $2$-nd plant using $f(2 - 1 + 1) = f(2) = 4$ millilitres of water.
   • water the $3$-rd plant using $f(3 - 1 + 1) = f(3) = 3$ millilitres of water.
   • water the $4$-th plant using $f(4 - 1 + 1) = f(4) = 16$ millilitres of water.
   • water the $5$-th plant using $f(5 - 1 + 1) = f(5) = 5$ millilitres of water.
2. The second operation will :
   • water the $2$-nd plant using $f(2 - 2 + 1) = f(1) = 1$ millilitres of water.
   • water the $3$-rd plant using $f(3 - 2 + 1) = f(2) = 4$ millilitres of water.
3. The third operation will :
   • water the $2$-nd plant using $f(2 - 2 + 1) = f(1) = 1$ millilitres of water.
   • water the $3$-rd plant using $f(3 - 2 + 1) = f(2) = 4$ millilitres of water.
   • water the $4$-th plant using $f(4 - 2 + 1) = f(3) = 3$ millilitres of water.
   • water the $5$-th plant using $f(5 - 2 + 1) = f(4) = 16$ millilitres of water.

Hence, the total amount of water in each plant is :

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

 

解题思路

  定义 $\text{lowbit}(x)$ 表示 $x$ 的二进制表示中最低位的 $1$ 所代表的值。因此，$f(x) = x \cdot \text{lowbit}(x)$。对于每次的区间加操作，由于每个位置 $i \in [l,r]$ 加的值 $f(i)$ 不一样，因此需要依次遍历每个位置来进行累加。

  本题的突破口在于需要注意到 $\text{lowbit}(x) = 2^{k} = 2^{k-1} + 2^{k-2} + \cdots + 2^{0} + 1$，其中 $k$ 是 $x$ 在二进制下最低位的 $1$ 所在的位数。那么 $$f(x) = x \cdot \text{lowbit}(x) = x \left(2^{k-1} + 2^{k-2} + \cdots + 2^{0} + 1\right)$$

  为了避免直接计算 $k$，注意到 $2^j \mid x \left(0 \leq j \leq k\right)$，而 $2^j \nmid x \left(j > k\right)$。因此我们只需考虑满足 $2^{j-1} \mid x \left(j \geq 1 \right)$ 的项，有 $$f(x) = x + \sum\limits_{j \geq 1, \, 2^j \mid x}{x \cdot 2^{j-1}} = \sum\limits_{j \geq 0, \, 2^j \mid x}{x \cdot 2^{\max\{0,j-1\}}}$$

  对于一个区间 $[l,r]$ 的操作，位置 $i$ 的偏移量是 $x = i-l+1$，代入到 $f(x)$ 得到 $$\sum\limits_{j \geq 0, \, 2^j \mid x}{x \cdot 2^{\max\{0,j-1\}}} = \sum\limits_{j \geq 0, \, 2^j \mid i-l+1}{i \cdot 2^{\max\{0,j-1\}}} - \sum\limits_{j \geq 0, \, 2^j \mid i-l+1}{(l-1) \cdot 2^{\max\{0,j-1\}}} \tag{1}$$

  对于某个固定的 $j$，只有当 $2^j \mid (i - l + 1)$ 时，位置 $i$ 才会受到贡献。这意味着，位置 $i$ 必须满足 $i \equiv l - 1 \pmod{2^j}$。具体来说，位置 $i$ 的值属于以下等差数列：$i \in \left\{ l-1+2^j, l-1+2 \cdot 2^j, l-1+3 \cdot 2^j, \dots,l-1+m \cdot 2^j \right\}$，其中 $m = \left\lfloor\tfrac{r-l+1}{2^j}\right\rfloor$。这样，区间内的位置根据模 $2^j$ 的结果被分成 $2^j$ 类，每一类的位置形成公差为 $2^j$ 的等差数列。因此，我们可以使用差分方法来更新每一类对应的区间。

  为了维护这个过程，定义差分数组 $d_1[j][i]$ 和 $d_2[j][i]$，分别表示公差为 $2^j$ 时，第 $i$ 个位置的差分值。这样，我们可以分别对式 $(1)$ 的前一项和后一项进行差分维护。对于区间 $[l, r]$ 的操作，有 $$\begin{equation*} \begin{cases} d_1[j][l-1+2^j] \gets d_1[j][l-1+2^j] + 2^{\max\{0,j-1\}} \\ d_1[j][l-1+(m+1) \cdot2^j] \gets d_1[j][l-1+(m+1) \cdot2^j] - 2^{\max\{0,j-1\}} \end{cases} \quad \begin{cases} d_2[j][l-1+2^j] \gets d_2[j][l-1+2^j] + (l-1) \cdot 2^{\max\{0,j-1\}} \\ d_2[j][l-1+(m+1) \cdot2^j] \gets d_2[j][l-1+(m+1) \cdot2^j] - (l-1) \cdot 2^{\max\{0,j-1\}} \end{cases} \end{equation*}$$

  接下来，定义关于 $d_1[j][i]$ 和 $d_2[j][i]$ 的前缀和 $s_1[j][i] = s_1[j][i - 2^j] + d_1[j][i]$ 和 $s_2[j][i] = s_2[j][i - 2^j] + d_2[j][i]$。那么对于位置 $i$，最后的答案就是 $s_1[j][i] \cdot i - s_2[j][i]$。

  AC 代码如下，时间复杂度为 $O(n \log{n})$：

#include <bits/stdc++.h>
using namespace std;typedef long long LL;const int N = 4e5 + 5;LL s1[18][N], s2[18][N];void solve() {int n, m;cin >> n >> m;for (int i = 0; 1 << i <= n; i++) {memset(s1[i], 0, n + 1 << 3);memset(s2[i], 0, n + 1 << 3);}while (m--) {int l, r;cin >> l >> r;for (int j = 0; 1 << j <= r - l + 1; j++) {int x = l - 1 + (1 << j);int y = l - 1 + ((r - l + 1 >> j) + 1 << j);int t = max(0, j - 1);s1[j][x] += 1 << t;s1[j][y] -= 1 << t;s2[j][x] += l - 1ll << t;s2[j][y] -= l - 1ll << t;}}for (int j = 0; 1 << j <= n; j++) {for (int i = 1 << j; i <= n; i++) {s1[j][i] += s1[j][i - (1 << j)];s2[j][i] += s2[j][i - (1 << j)];}}for (int i = 1; i <= n; i++) {LL ret = 0;for (int j = 0; 1 << j <= n; j++) {ret += s1[j][i] * i - s2[j][i];}cout << ret << ' ';}cout << '\n';
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int t;cin >> t;while (t--) {solve();}return 0;
}

 

参考资料

  Codeforces Round 1071 (Div. 3) Editorial：https://codeforces.com/blog/entry/149406