Substring 题解

题意简述

给定一个仅由 $1$ ~ $n$ 各一个的数列，有 $q$ 次询问,每次求这个数列字典序第 $k$ 小的非空子序列。

解法

前缀和加二分查找。

首先输入，同时进行预处理。建立数组 $b_{i}$ 记录每个数字 $i$ 在序列 $a$ 中的位置。数组 $sum_{i}$ 用于记录答案以 $i$ 为左端点 $l$ 时 $k$ 的最大值。

因此，有：

for(long long i=1ll;i<=n;i++)
{
    a[i]=getnum();
    b[a[i]]=i;
    sum[i]=sum[i-1]+(n-b[i])+1;
}

然后在询问时，对 $k$ 在 $sum$ 中进行二分查找，以确定左端点的值 $idx$ ，从而推导出位置 $l$ 为 $b_{idx}$ 。最后就可以推导出右端点的位置 $r$ 是 $b_{idx}+k-sum_{idx-1}-1$ 。(不会化简。。。)

注意由于 $1\le n,q\le 3\times 10^5$ ， $1\le k\le \dfrac{n(n+1)}{2}$ ，则有 $1\le k\le 4.5 \times10^{10}$ 。所以这里需要开 long long ,赛时就因为这个差点被卡了。。

AC code:

#include<bits/stdc++.h>
using namespace std;
long long a[3000001],b[3000001],n,m,q,idx,sum[3000001],k;
long long find(long long x)//二分查找
{
	long long l=1,r=n,mid;
	for(;l<=r;)
	{
		mid=(l+r)/2;
		if(sum[mid]>=k)
		{
			r=mid-1ll;
		}
		else
		{
			l=mid+1ll;
		}
	}
	return min(n,max(1ll,l));
}
long long get()//快读 
{
	long long x=0,f=1;
	char c;
	for(;;)
	{
		c=getchar();
		if(c=='-')
		{
			f=-1;
		}
		if(c>='0'&&c<='9')
		{
			break;
		}
	}
	for(;;)
	{
		x=x*10ll+(c-'0');
		c=getchar();
		if(c<'0'||c>'9')
		{
			break;
		}
	}
	return f*x;
}

signed main()
{
    n=get();
    q=get();
    for(long long i=1ll;i<=n;i++)
    {
    	a[i]=get();
    	b[a[i]]=i;
	}
	for(long long i=1ll;i<=n;i++)
	{
		sum[i]=sum[i-1]+(n-b[i])+1;//前缀和 
	}
	for(long long i=1ll;i<=q;i++)
	{
		k=get();
		idx=find(k);
		printf("%lld %lld\n",b[idx],b[idx]+k-sum[idx-1]-1ll);//输出左右端点 
	}
	return 0;
}

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