Decreasing String

题面翻译

有 $t$ 组测试点，每组测试点给出字符串 $s_1$ 和 一个整数 $pos$。

以下列规则得到字符串 $ S $ ：

• 从 $ s_{i - 1} $ 中删除一个字符，字典序最小的记为 $ s_i $
• $S = s_1 + s_2 + \dots + s_n $

输出字符串 $ S $ 第 $pos$ 个位置上的字符（即 $ S_{pos} $）。

题目描述

Recall that string $ a $ is lexicographically smaller than string $ b $ if $ a $ is a prefix of $ b $ (and $ a \ne b $ ), or there exists an index $ i $ ( $ 1 \le i \le \min(|a|, |b|) $ ) such that $ a_i < b_i $ , and for any index $ j $ ( $ 1 \le j < i $ ) $ a_j = b_j $ .

Consider a sequence of strings $ s_1, s_2, \dots, s_n $ , each consisting of lowercase Latin letters. String $ s_1 $ is given explicitly, and all other strings are generated according to the following rule: to obtain the string $ s_i $ , a character is removed from string $ s_{i-1} $ in such a way that string $ s_i $ is lexicographically minimal.

For example, if $ s_1 = \mathrm{dacb} $ , then string $ s_2 = \mathrm{acb} $ , string $ s_3 = \mathrm{ab} $ , string $ s_4 = \mathrm{a} $ .

After that, we obtain the string $ S = s_1 + s_2 + \dots + s_n $ ( $ S $ is the concatenation of all strings $ s_1, s_2, \dots, s_n $ ).

You need to output the character in position $ pos $ of the string $ S $ (i. e. the character $ S_{pos} $ ).

输入格式

The first line contains one integer $ t $ — the number of test cases ( $ 1 \le t \le 10^4 $ ).

Each test case consists of two lines. The first line contains the string $ s_1 $ ( $ 1 \le |s_1| \le 10^6 $ ), consisting of lowercase Latin letters. The second line contains the integer $ pos $ ( $ 1 \le pos \le \frac{|s_1| \cdot (|s_1| +1)}{2} $ ). You may assume that $ n $ is equal to the length of the given string ( $ n = |s_1| $ ).

Additional constraint on the input: the sum of $ |s_1| $ over all test cases does not exceed $ 10^6 $ .

输出格式

For each test case, print the answer — the character that is at position $ pos $ in string $ S $ . Note that the answers between different test cases are not separated by spaces or line breaks.

样例 #1

样例输入 #1

3
cab
6
abcd
9
x
1

样例输出 #1

abx

如果删掉一个字符得到的字符串是最小的，就删掉第一个降序得字符，比如haz，删掉h

const int N = 1e6 + 10;
int a[N];
void solve()
{
    string s; cin >> s;
    int x; cin >> x;
    int n = s.size();
    s = " " + s;
    if (n == 1)
    {
        cout << s[1];
        return;
    }
    deque<int> q;
    int h = 0;
    for (int i = 1; i <= n; i++)
    {
        while (q.size() && s[q.back()] > s[i])
        {
            a[++h] = q.back();
            q.pop_back();
        }
        q.push_back(i);
    }
    while (q.size())
    {
        a[++h] = q.back();
        q.pop_back();
    }
    int ans = 0;
    int top = n;
    int l = n, r = 1;
    int daan = n + 1;
    while (l >= r)
    {
        int mid = (l + r) / 2;
        if (x > (n + mid) * (n - mid + 1) / 2)
        {
            daan = mid;
            l = mid - 1;
        }
        else r = mid + 1;
    }
    ans = n - daan + 1;
    x -= (n + daan) * (n - daan + 1) / 2;
    map<int, int> p;
    for (int i = 1; i <= ans; i++) p[a[i]] = 1;
    for (int i = 1; i <= n; i++)
    {
        if (!p[i])
        {
            x--;
            if (x == 0)
            {
                cout << s[i];
                break;
            }
        }
    }
}
signed main()
{
    buff;
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}