第k小连续字串问题

· · 题解

【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 )即可。

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

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

代码

#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;
}