Problem Analysis: Digit DP

Before explaining the correct solution, let's first discuss the partial score approach.

For 50% of the data, where (1 \le L, R \le 10^6), a brute force simulation might be feasible. However, since we don't know the exact positions where each number appears, directly simulating with a 2D array is likely to cause memory issues (in fact, it does). Therefore, we need a different enumeration strategy. Notice that each number transforms into exactly one other number, and every number appears at least once (in the first column). Thus, we can recursively compute (cnt_{rev(i)} += cnt_i) and then use prefix sums for queries.

Below is the code for the 50% solution, which actually scores 80 points.

namespace p50 {
    const int N = 1e6;
    int cnt[N + 5];
    inline void init() {
        for (int i = 1; i <= N; ++i) ++cnt[i];
        for (int i = 1; i <= N; ++i) {
            int p = i + rev(i);
            if (p <= N) cnt[p] += cnt[i];
        }
        for (int i = 1; i <= N; ++i) cnt[i] += cnt[i - 1];
    }
    int main() {
        init();
        n = read();
        int l, r;
        for (int i = 1; i <= n; ++i) {
            l = read(); r = read();
            printf("%d\n", cnt[r] - cnt[l - 1]);
        }
    }
}

Now, let's discusss the correct solution.

For a given (x), define (y = x + rev(x)). Directly enumerating (x) is too slow, so we enumerate (y) instead. When (y) has 10 digits, if we temporarily ignore carries, the first five digits and the last five digits of (y) are symmetric. Except for the most significant digit (which also implies the least significant digit is non-zero), each digit can range from 0 to 18. Thus, there are (18 \times 19^4 = 2,345,778) possible combinations, which is manageable. Therefore, we use DFS to first determine the number of digits, then perform digit DP to enumerate each digit of (y).

Having enumerated the possibilities, we now need to count occurrences. Infact, during the DFS, we have already computed the number of times each (y) appears in the second column, because we enumerated (x + rev(x)). For later columns, since each number is derived from previous ones, we can iterate through all valid numbers. Since all possible numbers have been generated, we use an array sum to store the occurrence count of each number. Similar to before, we update (sum_{x+rev(x)} += sum_x - 1). We subtract 1 because the second row has already been accounted for. After computing prefix sums for sum, we can answer queries quickly.

There are minor implementation details, but the overall logic is as described.

#include<bits/stdc++.h>
#define ll long long
#define reg register
#define F(i,a,b) for(reg int i=(a);i<=(b);++i)
using namespace std;
bool beginning;
inline ll read();
const int M = 4e6 + 5, N = 20;
int n, cnt, p[N], q[N];
ll pw[N] = {1}, sum[M], a[M], tot[M], b[M];

inline ll rev(ll x) {
    ll ans = 0;
    while (x) ans = ans * 10 + x % 10, x /= 10;
    return ans;
}

void dfs(int n, int x, ll s, ll t) {
    if (x == (n + 1 >> 1)) {
        tot[++cnt] = t;
        b[cnt] = a[cnt] = s;  // store possible y values
        return;
    }
    for (int i = (x == 0); i <= 18; ++i) {
        if (n == (x << 1 | 1) and (i & 1)) continue;
        ll tmp = x ? p[i] : q[i];
        if (n == (x << 1 | 1)) tmp = 1;
        if (!tmp) continue;
        if (n == (x << 1 | 1))
            dfs(n, x + 1, s + pw[x] * i, t * tmp);
        else
            dfs(n, x + 1, s + (pw[x] + pw[n - x - 1]) * i, t * tmp);
    }
}

inline void init() {
    for (int i = 1; i <= 15; ++i) pw[i] = pw[i - 1] * 10;
    for (int i = 0; i <= 9; ++i)
        for (int j = 0; j <= 9; ++j)
            ++p[i + j], q[i + j] += (i != 0);
    // count combinations for each possible sum
    for (int i = 1; i <= 10; ++i) dfs(i, 0, 0, 1);
    // preprocessing
    int m = cnt;
    sort(a + 1, a + cnt + 1);
    cnt = unique(a + 1, a + cnt + 1) - a - 1;
    for (int i = 1; i <= m; ++i) {
        int pos = lower_bound(a + 1, a + cnt + 1, b[i]) - a;
        sum[pos] += tot[i];  // initial count
    }
    for (int i = 1; i <= cnt; ++i) {
        ll t = a[i] + rev(a[i]);
        int pos = lower_bound(a + 1, a + cnt + 1, t) - a;
        if (pos != cnt + 1 and a[pos] == t) sum[pos] += sum[i];
        ++sum[i];
        sum[i] += sum[i - 1];
    }
}

inline ll cal(ll x) {
    if (!x) return 0;
    int pos = upper_bound(a + 1, a + cnt + 1, x) - a - 1;
    return x + sum[pos] - pos;
}

bool ending;
int main() {
    init();
    n = read();
    ll l, r;
    for (int i = 1; i <= n; ++i) {
        l = read(); r = read();
        printf("%lld\n", cal(r) - cal(l - 1));
    }
    return 0;
}

inline ll read() {
    reg ll x = 0;
    reg char c = getchar();
    while (!isdigit(c)) c = getchar();
    while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    return x;
}

Accepted.