请统计某个给定范围[L, R]的所有整数中，数字2出现的次数。 比如给定范围[2, 22]，数字2在数2中出现了1次，在数12中出现1次，在数20中出现1次，在数21中出现1次，在数22中出现2次，所以数字2在该范围内一共出现了6次。 输入 输入共 1 行，为两个正整数 L 和 R，之间用一个空格隔开。 输出 输出共 1 行，表示数字 2 出现的次数。

算法1：暴力枚举

首先想到的是暴力枚举，对给定范围内的每个整数进行遍历，统计数字2出现的次数。

时间复杂度：O((R-L+1)log(R))，因为每个数的位数最多是log(R)，所以遍历每个数需要log(R)的时间复杂度，总共需要遍历R-L+1个数。

算法2：按位统计

观察数字2的性质，我们可以按位统计2出现的次数。

设当前位的值为digit，当前数的高位是high，当前数的低位是low，当前位是第i位。对于第i位上的数字2，它的取值范围有以下几种情况：

digit < 2，此时2不可能出现在第i位，这一位不贡献任何2的个数。

digit > 2，此时该位上的数字2出现次数为(high+1)*10^i。

digit = 2，此时该位上的数字2出现次数为high*10^i+low+1。

时间复杂度：O(log(R))，我们只需要枚举每一位，因此时间复杂度与数的位数有关，即log(R)。

算法3：数位dp

观察算法2的代码，我们可以发现对于digit = 2的情况，high和low的值需要递归地计算出来。因此我们可以使用数位dp的思想，通过递归实现按位统计的算法。

具体地，我们设函数solve(i,high)表示计算第i位至第0位的数字2出现次数，其中i表示当前位，high表示当前位及其高位组成的数。

当i=0时，solve(i,high)表示的是high的个位。如果该值小于2，表明2不可能出现在这一位，返回0；如果该值大于等于2，那么这一位上的数字2出现次数是high/10*10^i；如果等于2，我们需要统计low的数字2出现次数，递归计算solve(i-1,high)，但需要特别注意，当递归到i=0时，low的值应该是当前low-1，因为低位统计的范围是[0,low]。

我们需要计算的是[L,R]内所有整数的数字2出现次数，所以我们还需要加上R的数字2出现次数，即solve(log(R),R)-solve(log(R)-1,R)。

时间复杂度：O(log(R))，递归层数等于数的位数。