自动搬运

查看原文

来自洛谷，原作者为

	LinkZelda Be careful, Link.

搬运于2025-08-24 22:28:58，当前版本为作者最后更新于2021-02-11 23:17:05，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

• 做法简述：

题意十分清晰，就是给定一个数列，和一些断点，我们容易发现，把断点升序排序后，原数列分成了若干个区间，题目转化为求在每一个断开的区间内进行升序排序。

注意到题目给出的数据范围比较大：$N \leq 10^5$，使用冒泡排序，插入排序等是 $\mathit{O}(n^2)$ 的，不能通过。我们可以直接使用 algorithm 库中的 sort 排序，可以做到 $\mathit{O}(n \log n)$ 的复杂度，可以通过本题 。

• 代码如下 :

#include<cstdio>
#include<algorithm>
#include<ctype.h>
#define int long long

using namespace std;

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return x*f; 
 } 
 
int n,m,a[500005],b[500005];

signed main()
{
	n=read(),m=read();
	for(int i=1;i<=n;i++)
		a[i]=read();
	for(int i=1;i<=m;i++)
		b[i]=read();
	sort(b+1,b+m+1); // 记得排序后才能分成若干个区间
	b[m+1]=n; // 把最后一个断点设成 n , 实现起来会比较方便
	for(int i=0;i<=m;i++)
		sort(a+b[i]+1,a+b[i+1]+1);
	for(int i=1;i<=n;i++)
		printf("%lld ",a[i]);
	return 0;
}