思路与算法

令F(x)为0至x中各位不降的整数数量，区间答案为F(b)-F(a-1)。把x转成数字文本，从最高位往后填；状态记录位置pos、上一位last以及是否仍贴上界tight。下一位只能选择last至当前上界，转移后last变成所选数字。非贴上界状态按pos和last记忆化。

正确性说明

在每个前缀后，last准确记录上一位。只选择不小于last的数字，恰好保持不降条件；每个符合条件且不超过x的数字也有唯一逐位选择路径，所以无遗漏或重复。前导0不影响正整数的数位顺序，因为首个正数字之前全为0，不会额外限制它。数字0被F统一计一次，两个前缀相减时取消。由此得到闭区间计数。

复杂度

最多10位，状态为位置乘10个last，每状态至多试10个数字，总计算O(L1010)，每次清空固定11*10个缓存槽的初始化也已计入。空间为该110槽、数字文本及O(L)递归栈。每个区间调用两次，文件按EOF逐组处理。计数使用long long。

易错点

不降允许相等，446合法；123合法但321不合法。不要把输入整数a,b本身的顺序与数位不降混为一谈。上界可能是2^31-1，测试包含10位边界、单点、跨位数区间和重复查询。独立答案枚举1至10位的非降数字组合后按数值界二分。

参考代码（C++11）

#include <cstring>
#include <iostream>
#include <string>
using namespace std;
string digits;
long long memo[11][10];
long long visit(int pos, int last, bool tight) {
    if (pos == (int)digits.size())
        return 1;
    if (!tight && memo[pos][last] >= 0)
        return memo[pos][last];
    int upper = tight ? digits[pos] - '0' : 9;
    long long ans = 0;
    for (int d = last; d <= upper; ++d)
        ans += visit(pos + 1, d, tight && d == upper);
    if (!tight)
        memo[pos][last] = ans;
    return ans;
}
long long count(long long x) {
    if (x < 0)
        return 0;
    digits = to_string(x);
    memset(memo, -1, sizeof(memo));
    return visit(0, 0, true);
}
int main() {
    long long a, b;
    while (cin >> a >> b)
        cout << count(b) - count(a - 1) << '\n';
}