【MX-J3-T2】Substring

更好的阅读体验

题意简述

给你 $1$ 到 $n$ 的排列，求字典序第 $k$ 小的连续子串。

思路分析

以下“区间”，“子串”均指连续子串。

求第 $k$ 小，一个朴素的想法就是排序所有区间，然后输出第 $k$ 呗。

这样的时间复杂度是 $\Theta(n^2+q)$ 的，代码繁杂，此处不赘述。

但是我们这样考虑: 钦定一个区间，比如 $[i,n]$ ，由字典序的定义，他的所有前缀 $\forall i<j<n$ , $[i,j]$ 的字典序都小于他。也就是说，把所有区间排序输出， $[i,n]$ 一定在他的所有前缀后面。

而 $[i,n]$ 的所有前缀有 $n-i$ 个，也就是说以 $i$ 开头的所有子串的字典序排名是连续的，有 $n-i+1$ 个。

然后考虑区间左端点不同的情况，由于是排列，左端点不同就是最左的数字不同。所以我们可以先排个序，然后维护一个类似前缀和的数组 $\text{sum}[i]$ 表示区间 $[i,n]$ 的字典序排名。询问时在 $\text{sum}[i]$ 数组中二分左端点，快速计算右端点(即在左端点加上偏移量 $k-\text{sum}[pos-1]-1$ )即可。

排序之前要把原下标记录一下。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,sum[300005];
pair<int,int>a[300005];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i].first,a[i].second=i;
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
        sum[i]=sum[i-1]+n-a[i].second+1;
    for(int x;q--;){
        cin>>x;
        int pos=lower_bound(sum+1,sum+n+1,x)-sum;
        x-=sum[pos-1];
        cout<<a[pos].second<<" "<<a[pos].second+x-1<<"\n";
    }
    return 0;
}