题解思路

这道题要求我们计算区间[l,r]中有多少个整数是蛇形数，其中蛇形数定义为每一位数字都大于等于它右边的数字。

由于范围非常大$(l, r ≤ 10^{18})$ ，不能暴力枚举每个数字。这类题目可以使用数位DP（数字动态规划）来解决。

算法思路

1. 定义函数count(n)计算1到n范围内蛇形数的个数

题目内容

定义一个整数是蛇形数，当且仅当它的每一位都大于等于它的右边一位。例如，$8,31$和$220$是蛇形数，但$35$和$202$ 不是。

现在，你需要判定给定的区间$[l,r]$中，有多少个整数是蛇形数。

输入描述

在一行上输入两个整数$l,r(1≦l≦r≦10^{18})$ 代表一次查询。

输出描述

输出一个整数，代表该查询区间的蛇形数的个数

样例1

输入

3 28

输出

12

说明

其中，$3,4, 5, 6, 7, 8, 9,10,11,20,21,22$是蛇形数。