题目描述
给一个数组{a}，定义 h(a,b)为在十进制下 a + b 与 a 的位数差，求 ，0的位数为1。

输入描述: 

	
	
	
	
	
	

		第一行读入一个正整数 n (1 <= n <= 105)。
	


	

		第二行读入 n 个非负整数，第 i 个表示a[i] (0 <= a[i] <= 108)。

输出描述: 

一行表示答案。
示例1

输入 

10
0 1 2 3 4 5 6 7 8 9

输出 

20

题解

这道题要求我们求位数差，如果直接对每个数去求肯定不行，复杂度肯定爆炸。
所以换一个想法，我们按位去考虑。分别对每个数考虑每一位是否有贡献，比如我们举个例子。1，9，99三个数。对于1，我们先考虑十位，如果1要进到十位的话只要大于等于9就可以，我们发现大于等于9的数有两个，所以总答案加2；再考虑百位，如果要让1进位到百位的话，就需要大于等于99，总答案再加1，一次类推。
下面我们要解决的问题就是如何去查询能够让当前数进位的数的个数，我利用了树状数组去进行维护，（当然线段树也可以，不过树状数组好写啊QAQ）。除此之外还需要注意的一点就是数据范围到1e8，需要我们进行一下离散化。
当然这道题也可以分治去做，区间问题用分治还是挺多的，但我看其它大佬的题解已经讲过分治了就不再赘述了，祝大家AC愉快~

完整代码 

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+100;
#define ll long long
ll tree[N];
int a[N];
int b[9]={10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};
vector<int> v;
int n,m;
int where(int x){
    return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
int lowbit(int x){
    return -x&x;
}
void add(int x){
    while(x<=m){
        tree[x]++;
        x+=lowbit(x);
    }
}
int sum(int x){
    int num=0;
    while(x>0){
        num+=tree[x];
        x-=lowbit(x);
    }
    return num;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        v.push_back(a[i]);
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    m=v.size();
    ll ans=0;
    for(int i=n;i>0;i--){
        for(int j=0;j<8;++j){
            if(b[j]>a[i]){
                int l=where(b[j]-a[i]);
                ans+=sum(m)-sum(l-1);
            }
        }
        add(where(a[i]));
    }
    printf("%lld\n",ans);
}