Code For 1 题解
Zeng_Yi_Hang
·
·
题解
前言
古诗学习：
一头犁牛半块田，收也凭天，荒也凭天。
粗茶淡饭饱三餐，早也香甜，晚也香甜。
布衣得暖胜丝绵，长也可穿，短也可穿。
草屋茅舍有几间，行也安然，睡也安然。
雨过天晴驾小船，鱼在一边，酒在一边。
日上三竿犹在眠，不是神仙，胜是神仙。
省流：纯数学推公式
复杂度 O( \log n)
引理
本题要求我们拆出 \lfloor\frac{n}{2}\rfloor,n\bmod 2,\lfloor\frac{n}{2}\rfloor 三个数，因为 \lfloor\frac{n}{2}\rfloor=\lfloor\frac{n}{2}\rfloor 所以我们不难看出本题生成的答案树具有对称性，所以兄弟节点的答案相同。因此我们可以吧这个二叉树压缩为一个链，把 n\bmod 2 装入链中。
图例
我们用 n=7 举例
- 我们先画出 n=7 所生成的二叉树
- 然后把它压缩为一个链进行存储
- 我们把 a_1，a_2 挪到 a_3 层
这时我们很容易看出 [l,r] 内的 1 的数量要分层讨论，因为不同层数的模数并不相同。所以分层讨论是有必要的。
位置分析
由于 l,r 与当层节点的相对位置会对答案有影响，故接下来对它们的位置关系进行逆天分析。
引理
## 位置处理如下
由于只需要考虑 $r$ 与 $l$ 右侧第一个节点（若 $l$ 与当层某个节点重合，则 $l$ 也需取到）的相对位置，故可视作当层 $l$ 右侧第一个节点左侧全部被删除。
现已知需要**整体左移**一部分，那么需要**左移**多少呢？
首先，当层左端第一个节点的左侧会存在一些空槽位（若为最底层则没有），通过观察我们不难看出，这些空槽位的数目与层数是有一定关系的。假设最下层的层数是 $1$，总层数是 $cnt$，由下往上正在处理第 $i$ 层，则当层前置空槽位的数目为 $2^{i-1}-1$，所以我们先把这部分删去，即整体左移 $2^{i-1}-1$ 个槽位。
然后此时当层就是以一个节点为开头的了，那么 $l$ 左侧会有整数个循环区间，那么当层的循环区间长度为 $2^i$，那么左移长度是不是就等于
$$
\lceil \frac{l-2^{i-1}+1}{2^i} \rceil \times 2^i
$$
错！！！
如果此时 $l$ 刚好与当层某一个节点**重合**的话，它向上取整后则会**多删去一个区间**，所以我们做一点小调整：
把 $l-1$ 之后再去做这个算式是不是就正确了？
所以这个时候左移的**总位数**即是
$$
\lceil \frac{l-2^{i-1}}{2^i} \rceil \times 2^i+2^{i-1}-1
$$
所以更新后的**区间长度**即为
$$
r-\lceil \frac{l-2^{i-1}}{2^i} \rceil \times 2^i-2^{i-1}+1
$$
那这个时候如果你已经完全理解上述意思的话，我们是不是就可以看这个区间里有多少个循环区间？（注意：不完全取到的区间也要算上，因为只算区间头部的那一个节点，所以我们**向上取整**）
所以我们的最终答案为
$$
ans=\sum^{cnt}_{i=1}{ \lceil \frac{r-\lceil \frac{l-2^{i-1}}{2^i} \rceil \times 2^i-2^{i-1}+1}{2^i} \rceil \times a_{cnt-i+1}}
$$
（由于 $a$ 数组是**自上而下**存储的，所以求和的时候应该是 $a_{cnt-i+1}$）
## 最后附上 AC 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,l,r,a[105],cnt;
signed main()
{
cin>>n>>l>>r;
while(n)
{
a[++cnt]=n%2;
n/=2;
}
int ans=0;
int d=1;
for(int i=cnt;i>=1;i--)
{
d*=2;
int a1=ceil(double((l-d/2)*1.0/d))*d;
int a2=ceil(double((r-d/2+1-a1)*1.0/d));
ans+=a2*a[i];
}
cout<<ans;
return 0;
}
```
完结撒花！！！