P10995 【MX-J3-T2】Substring 题解

andycode · 2024-08-26 10:22:36 · 题解

题目传送门

题目大意

给出一个长度为 n 的序列 a，其中 1 \sim n 在序列 a 中各出现一次。

总共有 q 次询问，每次询问为序列 a 字典序第 k 小的子串的左右端点是多少。

思路讲解

设序列 x 为 a_{l_1 \sim r_1}、序列 y 为 a_{l_2 \sim r_2}，且序列 x 的长度不超过序列 y。

在对 x 和 y 的字典序进行比较时，不难发现：

• 如果 l_1=l_2 说明 x 为 y 的前缀，因为 x 的长度不超过 y 的长度，所以当 r_1 \ne r_2 时，x 的字典序小于 y 的字典序，否则 x 和 y 的字典序相等。

• 如果 l_1 \ne l_2，则可以直接比较 a_{l_1} 和 a_{l_2}，a_{l_1} 小则 x 的字典序小，否则 y 的字典序小。因为 1 \sim n 只会在 a 中出现一次，不会出现 a_i=a_j(1 \le i < j \le n) 的情况。

根据上面的结论，我们可以将 a 的所有子串通过开头数字进行分类，在每一类中将子串以长度从小到大排序。

设 p_i 为开头数字为 i 且长度为 1 的子串的字典序排名，b_i 为数字 i 在 a 中的下标，则可以很容易地得到 p_i 的递推公式。

对于每一次询问，由于 p_i 具有单调性，所以只需二分查找字典序第 k 小的子串属于哪一类，即第一个小于等于 k 的 p_i。找到后，左端点就是 b_i。由于每一类中的子串的字典序都是以长度排序，所以右端点为 b_i+k-p_i。

算法复杂度为 O(q \log{n})。

代码实现

#include <bits/stdc++.h>
using namespace std;
int n,q,a[300005],id[300005];
long long p[300005];
int main(){
    //p[i]=开头为i，长度为1的排名
    //id[i]为b[i]
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        id[a[i]]=i;
    }
    long long sum=1;
    for(int i=1;i<=n;i++){
        p[i]=sum;
        sum+=n-id[i]+1;
    }
    while(q--){
        long long t;
        cin>>t;
        int l=1,r=n;
        while(l<r){
            int mid=(l+r+1)/2;
            if(p[mid]<=t)
                l=mid;
            else
                r=mid-1;
        }
        cout<<id[l]<<' '<<id[l]+t-p[l]<<'\n';
    }
    return 0;
}

完结撒花！