题意：
已知对于任意的 X ，将其本身填入集合时，也需要将 [ x - lowbit(x) + 1 , x - 1] 重新填入集合。
给出 X 的最大值 N 和询问次数 K
共有两类询问
1.询问将 [ L , R ] 中所有数逐次填入集合时，一共对每个数字填入了多少次。
2.询问将 [ 1 , N ] 中所有数逐次填入集合时，数字 X 被填入了多少次。
思路：
注意到对于任意的 X 填入集合时，一共操作了 [ x - lowbit(x) + 1 , x - 1]的大小 + 1 个数，即 lowbit(x) 个数。
由此我们可以做出图，形似树状数组。
那么对于操作1
如果我们可以计算出lowbit(i)的前 N 项和，我们就可以通过前缀和的思想O(1)来求出答案。
如何求出lowbit的前N项和呢？
我们注意到对于任意一个数 X ，lowbit(X) = 以 X 为根的子树的子叶节点数。
我们又知道高度为 H 的满二叉树有 2^H 个子叶节点（H = 0，1，2.......）。
那么我们可以通过统计 1.......X 以内有多少个高度为 0，1，2.....的子树就可以计算出lowbit的前 X 项和是多少。统计的过程显然是 O(logX) 的。
所以对于操作1，其复杂度可以控制在O(logN)左右。
对于操作2，由图显然对于任意一个数 X 其插入的次数是其父节点的个数
例 1 4、6 2 、8 1
利用 lowbit 递加即可 复杂度为 O(logN)
以上本题的复杂度为 O(KlogN)
代码：
#include <bits/stdc++.h> using namespace std; long long lowbit(long long x){ return x&(-x); } long long solve(long long x){ long long ans=0,two=1; while(x!=0){ ans+=two*(x-x/2); x/=2; two*=2; } return ans; } int main() { long long n,x,y,ans; int m,ch; while(scanf("%lld%d",&n,&m)!=-1){ for(int i=0;i<m;i++){ scanf("%d",&ch); if(ch==1){ scanf("%lld%lld",&x,&y); ans=solve(y)-solve(x-1); }else{ scanf("%lld",&x); ans=0; while(x<=n){ ans++; x+=lowbit(x); } } printf("%lld\n",ans); } } }