Wannafly挑战赛3 C.位数差（二分+树状数组）

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 65536K，其他语言131072K
64bit IO Format: %lld
题目描述

给一个数组{a}，定义 h(a,b)为在十进制下 a + b 与 a 的位数差，求 ∑1≤i<j≤nh(ai,aj) ，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

求出每个数a[i]进1位~进9位所需要的值x是多少，然后二分得出最初位置i，加上i后有多少个数大于等于x,
记录i后有多少个大于等于x的值需要用树状数组维护

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+200;
int pos[N],a[N],b[N],tree[N],n;
long long s[15]={0,0,10};
int lowbit(int x)
{
    return x&-x;
}
void add(int i)
{
    for(; i<=n+55; i+=lowbit(i))
        tree[i]++;
}
int query(int i)
{
    int ans=0;
    for(; i; i-=lowbit(i))
        ans+=tree[i];
    return ans;
}
int ditnum(int x)
{
    int cnt=0;
    if(!x)cnt=1;
    while(x)
        x/=10,cnt++;
    return cnt;
}
int main()
{
    long long ans=0;
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
        b[i]=a[i];
    }
    sort(b+1,b+1+n);
    for(int i=3; i<=10; i++)
        s[i]=s[i-1]*10;
    for(int i=1; i<=n; i++)
        pos[i]=lower_bound(b+1,b+n+1,a[i])-b;

    for(int i=n;i>=1;i--)
    {
        int now=a[i],dit=ditnum(a[i]),cha;

        while(1)
        {
            ++dit;
            cha=s[dit]-a[i];
            int xia=lower_bound(b+1,b+1+n,cha)-b-1;
            if(xia==n)break;
            ans+=query(n)-query(xia);
        }

        add(pos[i]);
    }
    cout<<ans<<endl;
    return 0;
}