NC14380 位数差

#include <iostream>
#include <algorithm>
using namespace std;
int n;
const int maxn =1e5+7;
int arr[maxn];
int nums[9] = { 10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
long long solve(int l, int r) {
    if (l == r)return 0;
    int mid = l + (r - l) / 2;
    long long ans = solve(l, mid) + solve(mid + 1, r);
    sort(arr + mid + 1, arr + r + 1);
    for (int i = l; i <= mid; i++) {
        for (int j = 0; j < 9; j++) {
            if (nums[j] - arr[i] > 0) {
                ans += arr + r + 1 - lower_bound(arr + mid + 1, arr + r + 1, nums[j] - arr[i]);
            }
        }
    }
    return ans;
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    cout << solve(1, n);
}