自动搬运

查看原文

来自洛谷，原作者为

	yummy 这个人是时代的眼泪，什么也没有留下

搬运于2025-08-24 23:03:16，当前版本为作者最后更新于2024-08-25 18:58:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

B. Substring 官方题解

本题考察的主要知识点：

• 【3】递推法（前缀和）
• 【4】lower_bound 函数

思路分析

（为了防止双重下标，可能会用 $a[x]$ 表示 $a_x$。）

考虑如何比较 $a[l_1\sim r_1]$ 和 $a[l_2\sim r_2]$ 的字典序。

因为数列 $a$ 中 $1\sim n$ 各出现了一次，如果 $l_1\ne l_2$，那么 $a[l_1],a[r_2]$ 必然不同，比较它们即可。

否则一个字符串必然是另一个的前缀。如果 $r_1<r_2$ 则前者字典序小于后者，反之亦然。

使用这个方法可以把所有子串进行排序，根据选用排序方法的不同可得 $35\sim 45$ 分。

进一步思考，我们不求出所有子串，照样可以回答“第 $k$ 个子串是谁“的问题吗？

假设 $a_l=x$，记 $p_x=l$，即“$x$ 的位置是 $l$”，那么 $x$ 开头的子串就有 $n+1-p_x$ 个。

在读入整个 $a$ 后，我们对于所有 $i=1,2,\ldots,n$，知道了以 $i$ 开头的子串个数。进而作前缀和，对于所有 $i=1,2,\ldots,n$，可知开头 $\le i$ 的子串个数，记为 $c_i$。

对于一个问题，我们查找最小的 $l$ 使得 $c_l\ge k$，这样 $c_{l-1}+1\le k\le c_l$，左端点的数值就是 $l$ 了，左端点下标是 $p_l$。然后计算 $k-c_{l-1}$ 知区间长度，计算 $p_l+k-c_{l-1}-1$ 就可以求出右端点。

总时间复杂度 $O(n+q\log n)$。

参考代码

#include<bits/stdc++.h>
using namespace std;
int n,q,x,p[300005];
long long k,c[300005];
int main(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++){
		scanf("%d",&x);
		p[x]=i;
	}
	for(int i=1;i<=n;i++)
		c[i]=c[i-1]+n-p[i]+1;
	for(;q;q--){
		scanf("%lld",&k);
		int l=lower_bound(c,c+n+1,k)-c;
		printf("%d %lld\n",p[l],k-c[l-1]+p[l]-1);
	}
	return 0;
}