Easy vision：
维护三个数组 a[ ] , b[ ] , c[ ] ;
a[ i ] 表示 数值为 i 的数字的长度，例如 a [ 1 ] = 1 , a [ 23 ] = 2 ;
b[ i ] 表示 数字1~i 的总长度 ，例如 b[ 9 ] = 9 , b[ 11 ] = 13 (1234567891011) ;
c[ i ] 表示 序列 1~1 、1~2、…… 、1~i-1 、 1~ i ，长度总和，即为题目所描述序列， 例如 c[ 10 ] = 56;
由上述定义可知 b是a的前缀和，c是b的前缀和数组。
数据范围 k 是 1~1e9，而 i 的能够取得的最大值 < n * (n + 1) / 2 = k , 故 i < sqrt( k ) .所以数组肯定开的下。
输入长度 x ，因为前缀和具有单增的性质，可以二分c数组，划分出 x 在序列中属于 1~y（y>=x），即为在数组b中的索引y (注意b数组的定义，b [ y ] 表示 数字1~y 的总长度)； 然后再二分b数组，就能知道，他是属于哪个数字的了（设值数字为z），最后通过 a[ z ] 枚举位数即可求出答案。
AC代码
#include<bits/stdc++.h>
using namespace std;
const int N=5e4+5;
int a[N],b[N],c[N];
int read()
{
int x=0,t=1;
char ch=getchar();
while(!isdigit(ch)){ if(ch=='-')t=-1; ch=getchar(); }
while(isdigit(ch)){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
return x*t;
}
int main()
{
for(int i=1;i<=N;i++)///预处理
{
int x=i;
while(x)
{
x/=10;
a[i]++;
}
b[i]=b[i-1]+a[i];
c[i]=c[i-1]+b[i];
}
int T=read();
while(T--)
{
int n=read(),pos;
pos=lower_bound(c+1,c+N+1,n)-c;
n-=c[pos-1];// 减掉多余的 1~pos-1， 1~pos-2 …… 1~1 序列的长度，即定位到 1~pos
pos=lower_bound(b+1,b+N+1,n)-b;
n-=b[pos-1];// 同上，定位到 数值 pos
int ans=pos;
n=a[pos]-n; //因为序列是高位到低位，所以做了一下逆转；
while(n--) ans/=10; //枚举位数
printf("%d
",ans%10);
}
return 0;
}
Hard vision:
与上题一样的题意，但是数据范围变成了1e18 , 开方后是1e9 空间明显开不下。
所以需要对前缀和数组经过些许修改优化。明显的，之前a数组有很多连续项是相等的，因此可以用等差数列求和的思想，（每增加一个数字，在位数相同的固定区间内，长度增加的也是相同的），来重新定义这些数组。具体见代码注释。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=10;
LL a[15],b[15],c[15];
/// ai 表示位数是i的数字总长度；1~9 10~99 ...
/// b是a的前缀和 1~9 1~99 1~999 ...
/// c是序列总长度，等差数列求和
/// c1 1~1+1~2+...+1~9
/// c2 c1+ 1~10+1~11+...+1~99
/// c3 c1+c2+ 1~100+...+1~999
LL read()
{
LL x=0,t=1;
char ch=getchar();
while(!isdigit(ch)){ if(ch=='-')t=-1; ch=getchar(); }
while(isdigit(ch)){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
return x*t;
}
int main()
{
#define int LL
for(int i=1;i<=N;i++)
{
int x=i,l=1,r=0;
while(x--) l*=10,r=r*10+9;
l/=10;
a[i]=(r-l+1)*i;
b[i]=b[i-1]+a[i];///b 每次加一层的长度
c[i]=c[i-1]+(b[i-1]+i+b[i])*(r-l+1)/2;/// 1~1 -- 1~9 d=1; 1~10,1~11 -- 1~99 d=2; （d是公差）
///b[i-1]+i 是首项长度，b[i] 是末项长度，r-l+1 是 个数
}
int T=read();
while(T--)
{
int n=read();
int pos=lower_bound(c+1,c+N+1,n)-c;
n-=c[pos-1];
int l=1,r=0;
int x=pos,t=b[pos-1];
while(x--) l*=10,r=10*r+9;
l/=10;
int L=l;
while(l<=r)
{
int mid=(l+r)>>1;
int cnt=mid-L+1;
if( (2*t+pos+cnt*pos)*cnt/2>=n) r=mid-1;
else l=mid+1;
}
int cnt=l-L;
n-=(2*t+pos+cnt*pos)*cnt/2;
pos=lower_bound(b+1,b+N+1,n)-b;
n-=b[pos-1];
int ans=1;
for(int i=1;i<pos;i++) ans*=10;
t=(n-1)/pos;
n-=t*pos;
ans+=t;
n=pos-n;
while(n--) ans/=10;
printf("%lld
",ans%10);
}
return 0;
}