P10995 【MX-J3-T2】Substring

jjy2023 · 2024-08-25 19:32:45 · 题解

P10995 【MX-J3-T2】Substring

Description：

给你一个数列 a，求字典序第 k 小的子串的左右端点。

Solution：

可以使用前缀和来解决。记录每一个数的位置，将原数组进行排序，再将所有情况进行前缀和。在枚举时，注意到 O(mn) 的算法会超时，所以可以进行二分；枚举当左端点为 l，右端点为 r 时的情况总数为多少，最后再输出 l 以及下一项的前缀和 - 该项的前缀和再 -1 即可。最终时间复杂度为 O(m\log n)。

Code：

#include<bits/stdc++.h>
#define int long long//注意要开longlong
using namespace std;
int n,m,a[300005],aa[300005],b[300005],c[300005],d[300005];
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i],aa[i]=a[i],b[a[i]]=i;
    sort(aa+1,aa+n+1);
    for(int i=1;i<=n;i++) c[i]=n-b[aa[i]]+1,d[i]=d[i-1]+c[i];
    for(int i=1;i<=m;i++)
    {
        int x,sum=0,flag=0;
        cin>>x;
        int l=1,r=n;
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(d[mid]==x) {cout<<b[mid]<<' '<<n<<endl;flag=1;break;}
            else if(d[mid]>x) r=mid-1;
            else l=mid+1;
        }
        if(flag==0)
        {
            sum=d[r];
            cout<<b[l]<<' '<<b[l]+(x-sum-1)<<endl;
        }
    }
    return 0;
}