Numerical Sequence (easy version)

Created by LXC on Sat Mar 2 11:26:21 2024

https://codeforces.com/problemset/problem/1216/E1

ranting: 1900

tag: binary search, brute force, math

problem

给你一个形式为 “112123123412345 $\dots$ “的无穷序列，它由一个接一个的连续正整数块组成。第一个整数块由 $1$ 到 $1$ 的所有数字组成，第二个整数块由 $1$ 到 $2$ 的所有数字组成，第三个整数块由 $1$ 到 $3$ ， $\dots$ 的所有数字组成， 第$i$个整数块由 $1$ 到 $i$ 的所有数字组成。

所以序列的前 $56$ 个元素是 “11212312341234512345612345671234567812345678912345678910”。序列中的元素从 1 开始编号。例如，序列的 $1$ 个元素是 $1$ ，序列的 $3$ 个元素是 $2$ ，序列的 $20$ 个元素是 $5$ ，序列的 $38$ 个元素是 $2$ ，序列的 $56$ 个元素是 $0$ 。

你的任务是回答 $q$ 个独立的查询。在 $i$ -th查询中，你得到了一个整数 $k_i$ 。计算序列中位于 $k_i$ 位置的数字。

solution

离线处理q个查询。

我们维护1到i个数字长度的前缀和，为$p_i$，定义$s_i = \sum \limits_{j=1}^ip_j$

显然对于查询在$s_{i-1}$到$s_{i}$的数来说，可以直接在$p_i$上二分找到答案。

由于查询最多$n=10^9$我们最多只需要维护前$O(\sqrt n)$数量级的前p项和即可。时间复杂度$O(\sqrt n + qlog \sqrt n)$

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

void sol() {
    int n;
    cin >> n;
    vector<ll> a(n), idx(n);
    for (auto& i:a) cin >> i;
    int mx = *max_element(a.begin(), a.end());
    // int sz = (int) sqrt(mx+100);
    int sz = 1e5;
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int x, int y) {
        return a[x] < a[y];
    });
    vector<char> ans(n);
    int u = 0;
    ll s = 0;
    vector<int> p(sz);
    vector<string> num(sz);
    num[0] = "0";
    for (int i=1; i<sz && u < n; i++) {
        num[i] = to_string(i);
        p[i] = p[i-1]+num[i].size();
        s += p[i];
        while (u<n && a[idx[u]] <= s) {
            ll add = s-p[i];
            int l = 1, r = i+1;
            while (l<r) {
                int m = l+r>>1;
                if (p[m]+add >= a[idx[u]]) {
                    r = m;
                } else {
                    l = m+1;
                }
            }
            // 最后一个小于的位置
            ll ps = a[idx[u]] - (p[r-1]+add);
            // cout << ps << endl;
            ans[idx[u]] = num[r][ps-1];
            u++;
        }
    }
    for (auto i:ans) {
        cout << i << "\n";
    }
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}