位数差

大致题意：给定一个序列，求 .
表示 和 十进制下的位数差.

分析：
方法一:离散+树状数组
我们可以逆序遍历序列，计算当前 作为 的左参数的贡献，那么我们与 相加能产生数位差 .举个例子：能至少产生一位数位差，设比 大的最小十进制数位 ，那么 的大小一定要大于等于 .依次枚举至少产生两位数位差.....其实就是遍历所有的十进制数字进行查找.
那么当我们求解 的数位差贡献时，必须要有一个数据结构存储 ,并且使其有序才能进行二分查找符合条件的 的个数。-------离散所有可能出现的值(大概9e5)，然后树状数组维护即可.

#include<bits/stdc++.h>
#define lowbit(x) x&(-x)

using namespace std;

typedef long long ll;
const int maxn=2e5+10;
int a[maxn],sum[maxn*9];

int n;
vector<int> p;
vector<int> p1;
int cnt;
void add( int x ) { while( x<=cnt ) sum[x]++,x+=lowbit(x); }
int get_sum( int x ,int ans=0 ) { while( x ) ans+=sum[x],x-=lowbit(x);return ans; }

int get_id( int x )
{
    return lower_bound(p1.begin(),p1.end(),x)-p1.begin()+1;
}

int main()
{
    cin>>n;
    for( int i=1,num=10;i<=9;i++,num*=10 )  p.push_back(num);
    for( int i=1;i<=n;i++ ) scanf("%d",&a[i]);

    for( int i=1;i<=n;i++ )
    {
        for( int j=0;j<9;j++ )   if( a[i]>p[j] )  p1.push_back(p[j]-a[i]);
        p1.push_back(a[i]);
    }
    sort(p1.begin(),p1.end());
    cnt=p1.size();

    ll ans=0;
    for( int i=n;i>=1;i-- )
    {
        for( int j=0;j<9;j++ )
        {
            if( a[i]>=p[j] ) continue;
            int pos=get_id(p[j]-a[i]);
            ans+=get_sum(cnt)-get_sum(pos-1);  
        }
        add(get_id(a[i]));
    }
    printf("%lld\n",ans);
}

方法二：分治
二分区间长度，分治每个区间的数位差贡献，合并计算时，对于当前左右区间，对右区间进行排序，遍历左区间 进行求 在右区间符合条件的个数。查找条件和方法一类似。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn=2e5+10;
int a[maxn],sum[maxn];

ll b[10];

ll solve( int l,int r )
{
    if( r==l ) return 0;
    int mid=(l+r)/2;
    ll res=solve(l,mid)+solve(mid+1,r);
    sort(a+mid+1,a+r+1);
    for( int i=l;i<=mid;i++ )
    {
        for( int j=0;j<9;j++ ) 
        {
            if( b[j]-a[i]>0 ) 
            res+=a+r+1-lower_bound(a+mid+1,a+r+1,b[j]-a[i]);
        }
    }
    return res;
}


int main()
{
    int n;cin>>n;b[0]=10;for( int i=1;i<9;i++ ) b[i]=b[i-1]*10;
    for( int i=1;i<=n;i++ ) cin>>a[i];
    cout<<solve(1,n)<<endl;
}