题面
我们定义一个数是单调数，当且仅当构成这个数每一个数位都是单调不降或不增的。
例如 \(123\) 和 \(321\) 和 \(221\) 和 \(111\) 是单调的，而 \(312\) 不是单调的。
给定 \(T\) 组 \(l, r\)，每次询问 \([l, r]\) 中有几个单调的数。
\(l, r \le 10 ^ {18}, T \le 10^4\)
题解
今天 hihoCoder 竟然 \(AK\) 了，真舒服（虽然题目很水，还被罚时坑惨了）qwq
显然考虑一个数位 \(dp\) ，不难发现我们只需要记下当前在哪一位，以及最后一位是什么数字就行了。
然后对于不降和不增做个两遍就行了，但有很多细节后面细讲。
写的时候发现自己摸索了一套数位 \(dp\) 的套路？（逃
套路：
我们常常是要求 \(\le n\) 的有多少个满足要求的数。
这个限制有些恶心，我们需要多一位来看是否被限制。
我们一般按位考虑，令 \(dp[i][0 / 1]\) 为到从高到低考虑到第 \(i\) 位，当前有/没被 \(n\) 限制。
我们考虑把 \(n\) 按位拆下来，变成一个数组
lim[i]，然后取出 \(n\) 的位数Bit。每次考虑后一位放什么数字就行了。具体实现如下（用刷表法方便转移）：
dp[0][0] = 1;for (int i = 0; i < Bit; ++ i) for (int now = 0; now <= 1; ++ now) for (int dig = 0; dig <= 9; ++ dig) if (now || (dig <= lim[i + 1])) dp[i + 1][now || (dig < lim[i + 1])] += dp[i][now];然后最后的答案就是
ans = dp[Bit][0] + dp[Bit][1];不难发现这样写，每个位数的数都会被考虑到。因为我们枚举的时候允许了前缀 \(0\) 的存在。
并且如果存在前缀 \(0\) 那么后面的所有数都不会存在限制了，可以随便填。
但是注意这样的话，全部为 \(0\) 的也会考虑进去，我们平常要考虑是否 \(-1\) 就行了。
对于这道题我们可以类比这种方法去做。
首先把答案差分表示 \(ans = ans_r - ans_{l - 1}\) 。
然后令 dp[i][j][0/1] 为到第 \(i\) 位，最后一次填 \(j\) ，有/没 被 \(n\) 限制住的情况。
直接这样写的话，递增是没有问题的，递减的时候就会存在问题了。
因为我们把前导 \(0\) 考虑进去了，结果导致没有正确算上这部分贡献。
所以我们还要多一维，也就是 dp[i][j][0/1][0/1] 前三个同上，最后一个意义是当前完全不/是前缀 \(0\) 。
然后转移的时候也是枚举数字，然后按照两种情况考虑下填的这个数的限制就行了。
注意有一些数会被递增递减算两次，也就是 \(111\) ，\(3333\) ，这些完全相同的数。可以直接暴力枚举减去就行了。
复杂度是 \(O(T * 18 * 10)\) 的。
总结
碰到数位 \(dp\) 直接上套路去讨论。
然后就需要对于具体问题具体分析了，根据题目要求设出需要的状态。
有时候可以根据需要卡卡状态数，因为通常不可能到满。
一定要写个暴力拍，这个东西其实很好调？
代码
建议看看代码，其实写的很简洁？（可读性也是很鲁棒的qwq）
#include#define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)#define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)#define Set(a, v) memset(a, v, sizeof(a))#define Cpy(a, b) memcpy(a, b, sizeof(a))#define debug(x) cout << #x << ": " << x << endl#define DEBUG(...) fprintf(stderr, __VA_ARGS__)using namespace std;inline bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;}inline bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}inline int read() { int x = 0, fh = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') fh = -1; for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48); return x * fh;}void File() {#ifdef zjp_shadow freopen ("1770.in", "r", stdin); freopen ("1770.out", "w", stdout);#endif}typedef long long ll;ll dp[19][10][2][2];int lim[19];inline int Get_Bit(ll x) { int tot = 0; for (; x; x /= 10) lim[++ tot] = x % 10; reverse(lim + 1, lim + tot + 1); return tot;}inline ll Calc(ll n) { if (!n) return 0; ll ans = 0; For (opt, 0, 1) { Set(dp, 0); dp[0][0][0][1] = 1; int Bit = Get_Bit(n); For (i, 0, Bit - 1) For (j, 0, 9) For(now, 0, 1) For (fir, 0, 1) { For (dig, opt ? 0 : j, opt ? (fir ? 9 : j) : 9) if (now || dig <= lim[i + 1]) dp[i + 1][dig][now || (dig < lim[i + 1])][fir && !dig] += dp[i][j][now][fir]; } For (j, 0, 9) For(now, 0, 1) For (fir, 0, 1) ans += dp[Bit][j][now][fir]; -- ans; } For (dig, 1, 9) { ll tmp = dig; while (tmp <= n) -- ans, tmp = tmp * 10 + dig; } return ans;}int main() { File(); for (int cases = read(); cases; -- cases) { ll l, r; cin >> l >> r; printf ("%lld\n", Calc(r) - Calc(l - 1)); } return 0;}