题目描述
你面前的黑板上写了 $[1,n]$ 中的所有正整数各一个。你的手里有一个计数器 $cnt$，初始为 $0$。
每次，你会选择黑板上最小的数 $x$（若有多个相同，只选择其中一个），并执行如下操作：
- 如果 $x=1$，那么直接将其从黑板上擦除；
- 否则，将 $cnt$ 加上 $(x\bmod 2)$ 的值，并擦除 $x$，然后写上两个 $\lfloor\frac{x}{2}\rfloor$。
请求出：当黑板上的数字全部被擦除时，$cnt$ 的值。
数据范围：$1\le n\le 10^9$。
解析
Update on 2025/8/11：同机房同学给出了一种极简做法，写在这里：
开始时，所有数的值之和为 $\displaystyle\sum_{k=1}^{n}k=\frac{n(n+1)}{2}$。
记 $\text{highbit}(i)$ 为 $i$ 的二进制最高位的值，则 $Ans=\displaystyle\frac{n(n+1)}{2}-\sum_{i=1}^{n}\text{highbit}(i)$。
显然 $\displaystyle\sum_{i=1}^{n}\text{highbit}(i)=\sum_{j\ge 0,2^j\le n}\Big(\min(2^j,n-2^j\color{red}{+1})\times 2^j\Big)$。
然后算这个式子就可以了，时间复杂度 $\mathcal{O}(\log n)$。
Part 1
我们显然不能直接暴力枚举。
定义“初始数字”为在所有操作开始前，写在黑板上的数字。我们注意到，处理时，任意两个初始数字不互相影响。也就是说，我们可以假设开始前黑板上只有一个数字 $i$（$1\le i\le n$），记此时最终的 $cnt$ 为 $cnt_i$，则 $Ans=\displaystyle\sum_{i=1}^{n}cnt_i$。
Part 2
我们思考一下求 $cnt_i$ 的过程到底是在干什么。设当前 $i=x$。
我们实际在干这么一件事：
- 维护一个权值 $w$，初始 $w=2^0$（即 $1$）。
- 重复执行如下操作：
- 如果 $x=1$，那么结束整个流程；
- 否则，$cnt\leftarrow cnt+(x\bmod 2)\times w$，然后 $x\leftarrow\lfloor\frac{x}{2}\rfloor$，$w\leftarrow w\times 2$（也就是将 $x$ 右移一位，将 $w$ 左移一位）。
容易发现，在第 $j$ 次操作中，$w=2^{j-1}$，$(x\bmod 2)$ 的值对应初始 $x$ 中 $2^{j-1}$ 位置的值。这个结论在正解中有用，先记着。
这样我们就有时间复杂度 $\mathcal{O}(n\log n)$ 的做法了，但这还不够。
Part 3
我们把上面的过程改一下，不是枚举数而是枚举二进制位。
根据 Part 2 中我们得到的结论，我们容易得到：$2^{j-1}$ 位置对最终答案的贡献为 $(cnt_A-cnt_B)\times 2^{j-1}$，其中：
- $cnt_A$ 是 $[1,n]$ 中的所有整数中，二进制位中 $2^{j-1}$ 位置为 $1$ 的数的个数；
- $cnt_B$ 是 $[1,n]$ 中的所有整数中，以 $2^{j-1}$ 为二进制最高位的数的个数。
如何快速求出 $cnt_A$ 与 $cnt_B$ 呢？
我们记 $q=\displaystyle\bigg\lfloor\frac{x}{2^j}\bigg\rfloor$，$r=x\bmod 2^j$。
显然，如果 $q=0$，那么 $n$ 的最高位一定是 $2^{j-1}$。根据上面的式子，显然 $2^{j-1}$ 位置对答案的贡献为 $0$，因此我们只需循环到最大的 $j$ 使得 $2^j\le n$ 即可。
先记一个小结论：
$[1,2^j-1]$ 中有且只有 $[2^{j-1},2^j-1]$ 的 $2^{j-1}$ 位置为 $1$。
有了上面的限制，我们计算出的 $q$ 一定是正数，且显然有 $cnt_B=2^{j-1}$（理由：$2^j\le n$ 和上面的小结论）。我们只需考虑如何计算 $cnt_A$ 即可。
$cnt_A$ 分布在两部分中：被 $2^j$ 整除的部分（由 $q$ 代表）和整除完剩余的部分（由 $q$ 代表）。
- 对于每个整除产生的 $2^j$ 大小的块，根据上面的小结论，每个块对 $cnt_A$ 有恰好 $2^{j-1}$ 的贡献，因此这部分的总贡献就是 $q\times 2^{j-1}$；
- 对于剩余部分，还是根据上面的小结论，只有 $\ge 2^{j-1}$ 的部分会对 $cnt_A$ 有贡献，因此这部分的总贡献就是 $\max(0,r-2^{j-1}+1)$。
所以 $cnt_A=q\times 2^{j-1}+\max(0,r-2^{j-1}+1)$。
也就是说，第 $2^{j-1}$ 位对答案产生的贡献为 $\Big((q-1)\times 2^{j-1}+\max(0,r-2^{j-1}+1)\Big)\times 2^{j-1}$。
整合一下：(完全展开形式）
$$Ans=\displaystyle\sum_{j\gt 0,2^j\le n}\Bigg(2^{j-1}\times\bigg(\Big(\big\lfloor\frac{n}{2^j}\big\rfloor-1\Big)\times 2^{j-1}+\max\Big(0,(n\bmod 2^j)-2^{j-1}+1\Big)\bigg)\Bigg)$$
显然每一位的贡献可以时间复杂度 $\mathcal{O}(1)$ 完成，于是我们成功地把最终的时间复杂度降到了 $\mathcal{O}(\log n)$。
AC Code
按最终的式子计算就可以了，所以不展示。
乘法一定一定开 long long！！！ 不长记性
后记
感谢您的阅读！若有不妥之处还请批评指正！