题解：P10995 【MX-J3-T2】Substring

· · 题解

B. Substring 官方题解

本题考察的主要知识点：

思路分析

（为了防止双重下标，可能会用 a[x] 表示 a_x。）

考虑如何比较 a[l_1\sim r_1] 和 a[l_2\sim r_2] 的字典序。

因为数列 a 中 1\sim n 各出现了一次，如果 l_1\ne l_2，那么 a[l_1],a[r_2] 必然不同，比较它们即可。

否则一个字符串必然是另一个的前缀。如果 r_1<r_2 则前者字典序小于后者，反之亦然。

使用这个方法可以把所有子串进行排序，根据选用排序方法的不同可得 35\sim 45 分。

进一步思考，我们不求出所有子串，照样可以回答“第 k 个子串是谁“的问题吗？

假设 a_l=x，记 p_x=l，即“x 的位置是 l”，那么 x 开头的子串就有 n+1-p_x 个。

在读入整个 a 后，我们对于所有 i=1,2,\ldots,n，知道了以 i 开头的子串个数。进而作前缀和，对于所有 i=1,2,\ldots,n，可知开头 \le i 的子串个数，记为 c_i。

对于一个问题，我们查找最小的 l 使得 c_l\ge k，这样 c_{l-1}+1\le k\le c_l，左端点的数值就是 l 了，左端点下标是 p_l。然后计算 k-c_{l-1} 知区间长度，计算 p_l+k-c_{l-1}-1 就可以求出右端点。

总时间复杂度 O(n+q\log n)。

参考代码

#include<bits/stdc++.h>
using namespace std;
int n,q,x,p[300005];
long long k,c[300005];
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        p[x]=i;
    }
    for(int i=1;i<=n;i++)
        c[i]=c[i-1]+n-p[i]+1;
    for(;q;q--){
        scanf("%lld",&k);
        int l=lower_bound(c,c+n+1,k)-c;
        printf("%d %lld\n",p[l],k-c[l-1]+p[l]-1);
    }
    return 0;
}