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