区间问题用分治还是挺多的，由于i < j的限制，这里实际上是相当于求“顺序对”（也就是后面的数更大的一对数字，而且还要求这两个数字加起来比起左边那个进位），实际上使用线段树或者树状数组的方法本质上还是属于分治值，在这里不在赘述。这里重点说一下普通的分治方法

对于这种区间题，我们会想什么前缀和，滑动窗口利用（这题还真有），单元素开始考虑等等。但是这道题和普通的区间还不同，因为它本质上求的是两个元素而不是一个区间内部的性质。而且求的是一个和，这个和也很难与任何东西产生二分关系。直接跑n2肯定tle。我们考虑到这个是单向的（也就是i < j的限制），对于一个数字的处理，他后面的数实际上就相当于没有用了，如果可以排序一下的话。使用lower_bound加一下速找到第一个可以进位的元素，那么后面的元素都可以进位了。（实际上我感觉这题与二分关系最大的就是这个lower_bound了）我们不可能对于每个数字k都对他后面的数字排一下序，就只能退而求其次的使用分治算法了

我们要明白：每个区间被分为两半后，逆序对只有两种情况：自己内部的（使用迭代实现）与一个在左区间一个在右区间的（我们刚才说的办法），对于每个数字。我们要看他是否可以与后面的数字进位，考虑到可能不止进了一位，我们可以提现先备好10,100,1000一直到1e8的8个数字the10num，对于每个数字k都去找他的the10num - k（当然前提是大于0才有正确的位数差）。对于右边的一个数字nr，假设他可以和数字k结合成超越10000，那他在前面的10,100,1000一定都会被一并合在后面的数字里计算。也就是说该算的位次贡献一个都不会少！（真的很神奇吧，这也是打算法为数不多让人感到有意思的地方）

AC代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;

int n;

vector<int> thenum(1e5 + 7,-1);
//忘了这里不能用n要不然全re了，全局可以选择开完也可以选择读取n后调整大小

int the10num[8] = {10,100,1000,10000,100000,1000000,10000000,100000000};

int calc(int l,int r)
{
    if(l == r)
    {
        return 0;//与自己当然是0
    }
    
    int mid = (l + r) / 2;
    
    int ans = calc(l,mid) + calc(mid + 1,r);
    
    sort(thenum.begin() + mid + 1,thenum.begin() + r + 1);//对右半部分进行排序
    
    //对于跨越左右的数对：
    
    for(int k = l;k <= mid;k++)
    {
        for(int h = 0;h < 8;h++)
        {
            if(the10num[h] - thenum[k] > 0)
            {
                auto endit = thenum.begin() + r + 1;//用index计算数量当然要多开一位
                
                auto pos = lower_bound(thenum.begin() + mid + 1,endit,the10num[h] - thenum[k]);
                
                ans += (endit - pos);//两个迭代器减出int了，嗯，很神奇吧
            }
        }
    }
    
    return ans;
}

signed main() 
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    cin>>n;
    
    for(int r = 0;r < n;r++)
    {
        cin>>thenum[r];
    }
    
    int cans = calc(0,n - 1);

    cout<<cans<<endl;
    
    return 0;
}

神秘小内容：static_cast(floor(log10(n))) + 1还有log10的关键词啊，可以快速计算一个数字的位次是多少（虽然这道题用不上就是了）