题目描述

小红有一个长度为n且值都为0的数组a。对于这个致组小红每次操作可以选择一个区间[l, r]，对于[l,r]上的每一个数牛必须让其加一或者乘二(元素之间操作独立，可以选择些元素乘二，一些元素加一，但是区间内每个元素都要操作)

题目思路

原题的答案有问题，有一种简单的方法是求出每个数最少需要多少次变换从0得到，求出最大的数量，然后每次都[1, n]所有元素进行操作，执行最大数量就可以得到结果，那些所需操作更少的数只需要在一开始为0的时候不停的乘以2即可，这样就还是0.

但是原题可能认为第一个操作不能是乘以2，所以只能通过相邻两个数的操作次数的差值来求解，假设第i个数的操作次数是x，第i+1个数的操作次数为y，如果y大于x，那么i+1和i这两个数可以共用x次操作，还需要y-x次的操作。如果y小于x，那么y就可以共享所有x的操作，这里记差值为0。所以直接将相邻数的操作次数的差值累加即可。

关于每个数的操作次数：只需要将每个数的二进制的1的数量和其最大位的位置相加即可，1的数量对应于+1，最大位置意味着*2（左移一位）。

代码