POJ 1019 Number Sequence：二分查找定位數字位置

POJ 1019 Number Sequence：二分查找定位數字位置

序列 S = S1 S2 ... Sk，其中 Sk = "123...k"。給定位置 i (≤ 2^31-1)，求該位置上的數字。需兩次二分：先定組，再定數，最後定位數字。

序列結構分析

• a[k]：Sk 的長度 = Σ_{j=1}^k len(j)，其中 len(j) 為 j 的十進制位數。
• b[k]：前 k 組總長度 = Σ_{j=1}^k a[j]。

預計算 a[]、b[] 至足夠大（如 40000）覆蓋最大查詢位置。

兩級二分查找

1. 第一層：在 b[] 中二分，找到包含位置 m 的組編號 k（使 b[k-1] < m ≤ b[k]）。
2. 第二層：在組 k 內，位置 p = m - b[k-1]。遍歷 1..k 累加位數，找到具體數字 num 及其內部偏移，取對應數字。

完整代碼（C++）

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
const ll maxn = 40000;
ll a[maxn], b[maxn];

void init() {
    a[1] = b[1] = 1;
    for (ll i = 2; i < maxn; i++) {
        a[i] = a[i-1] + (int)log10((double)i) + 1;
        b[i] = b[i-1] + a[i];
    }
}

ll f(ll m) {
    ll i = 1;
    while (b[i] < m) i++;
    int p = m - b[i-1];
    int len = 0;
    for (i = 1; len < p; i++)
        len += (int)log10((double)i) + 1;
    return (i-1) / (int)pow(10.0, len - p) % 10;
}

int main() {
    init();
    int T; cin >> T;
    while (T--) {
        ll n; cin >> n;
        cout << f(n) << endl;
    }
    return 0;
}

關鍵細節

• log10(i) + 1 計算整數位數，注意 i=1 時 log10(1)=0 正確得到 1 位。
• 預計算上限 maxn=40000 經驗值，實際 b[31267] ≈ 2.14e9 已覆蓋 2^31-1。
• 第二層查找可優化為二分，但線性遍歷 k ≤ 31267 足夠快。

範例驗證

輸入 8：序列前 8 位 11212312，第 8 位為 2。
輸入 3：第 3 位為 2。

複雜度

• 預處理：O(maxn)。
• 單次查詢：O(log maxn + k) ≈ O(√m)，極快。

此題展示了「預計算 + 多級二分」處理大數據區間定位的經典套路，核心在於建立正確的長度前綴和模型。