我的算法其实主要是利用一些数学知识。

对于任意的正整数 n,
记字符序列 n 为 a(n),
记字符序列 123456...n 即 a(1)a(2)...a(n) 为 b(n),
记字符序列 112123...n 即 b(1)b(2)...b(n) 为 c(n),
记 a(n) 的长度为 la(n),
记 b(n) 的长度为 lb(n),
记 c(n) 的长度为 lc(n),
注意到 c(n) 就是题目中的序列。

为了得到 c 序列中的第 i 位, 可以先找到第 i 位所在的 b 序列,
设 c 序列的第 i 位在 b(n+1) 序列,
则 lc(n) < i <= lc(n+1)，即 lc(n) <= i-1 < lc(n+1),
计算方程 lc(x) = i-1 的正根，向下取整即为 n,
问题就转化为得到 b 序列中的第 (i-lc(n)) 位.

为了得到 b 序列中的第 i 位, 可以先找到第 i 位所在的 a 序列,
设 b 序列的第 i 位在 a(n+1) 序列,
则 lb(n) < i <= lb(n+1)，即 lb(n) <= i-1 < lb(n+1),
计算方程 lb(x) = i-1 的根，向下取整即为 n,
问题就转化为得到 a 序列中的第 (i-lb(n)) 位.

求 a 序列中的第 k 位的方法略。

对于一个正整数 n,我们分类讨论:
A:  1 <= n < 10
    la(n) = 1
    lb(n) = Σ(la(k)) (k=1...n)
          = Σ(1) (k=1...n)
          = n
    lc(n) = Σ(lb(k)) (k=1...n)
          = Σ(k) (k=1...n)
          = (n+1)*n/2
    lb(9) = 9
    lc(9) = 45
    解方程 lc(x) = i-1 得
    x = sqrtl(i*2-1.75)-.5
    解方程 lb(x) = i-1 得
    x = i

B: 10 <= n < 100
    la(n) = 2
    lb(n) = Σ(la(k)) (k=1...n)
          = lb(9) + Σ(la(k)) (k=10...n)
          = 9 + Σ(2) (k=10...n)
          = 2n-9
    lc(n) = Σ(lb(k)) (k=1...n)
          = lc(9) + Σ(lb(k)) (k=10...n)
          = 45 + Σ(2k-9) (k=10...n)
          = (n-8)*n+36
    lb(99) = 189
    lc(99) = 9045
    解方程 lc(x) = i-1 得
    x = sqrtl(i-21)+4
    解方程 lb(x) = i-1 得
    x = (i+10)/2

C: 100 <= n < 1000
    la(n) = 3
    lb(n) = Σ(la(k)) (k=1...n)
          = lb(99) + Σ(la(k)) (k=100...n)
          = 189 + Σ(3) (k=100...n)
          = 3n-108
    lc(n) = Σ(lb(k)) (k=1...n)
          = lc(99) + Σ(lb(k)) (k=100...n)
          = 9045 + Σ(3k-108) (k=100...n)
          = (n*3-213)*n/2+4887
    lb(999) = 2889
    lc(999) = 1395495
    解方程 lc(x) = i-1 得
    x = (sqrtl(i*6-17985.75)+106.5)/3
    解方程 lb(x) = i-1 得
    x = (i+110)/3

D: 1000 <= n < 10000
    la(n) = 4
    lb(n) = Σ(la(k)) (k=1...n)
          = lb(999) + Σ(la(k)) (k=1000...n)
          = 2889 + Σ(4) (k=1000...n)
          = 4n-1107
    lc(n) = Σ(lb(k)) (k=1...n)
          = lc(999) + Σ(lb(k)) (k=1000...n)
          = 1395495 + Σ(4n-1107) (k=1000...n)
          = (n*2-1105)*n+503388
    lb(9999) = 38889
    lc(9999) = 189414495
    解方程 lc(x) = i-1 得
    x = sqrtl(i*.5-175385.4375)+276.25
    解方程 lb(x) = i-1 得
    x = (i+1110)/4

E: 10000 <= n < 100000
    la(n) = 5
    lb(n) = Σ(la(k)) (k=1...n)
          = lb(9999) + Σ(la(k)) (k=10000...n)
          = 38889 + Σ(5) (k=10000...n)
          = 5n-11106
    lc(n) = Σ(lb(k)) (k=1...n)
          = lc(9999) + Σ(lb(k)) (k=10000...n)
          = 189414495 + Σ(5n-11106) (k=10000...n)
          = (n*5-22207)*n/2+50488389
    lb(99999) = 488889
    lc(99999) = 23939649495
    解方程 lc(x) = i-1 得
    x = sqrtl(i*.4-15263847.51)+2220.7
    解方程 lb(x) = i-1 得
    x = (i+11110)/5

注意到 lc(99999) > 2147483647, 所以 n < 100000, 不需要继续分类了.