（2022杭电多校六）1012-Loop（单调栈+思维）

题目：

 样例输入：

2
7 3
1 4 2 1 4 2 4
5 2
4 3 5 4 5

样例输出：

4 4 2 4 2 1 1
5 4 5 4 3

题意：给定一个长度为n的序列，我们要对这个序列进行操作，每次操作我们每次可以选择一个区间[l,r]，使得区间[l+1,r]的数整体左移一个单元，然后第l个数挪至第r个数的位置，我们可以进行k次操作，让我们输出k次操作后得到的字典序最大的序列。

分析：仔细分析一下这个操作的本质其实就是把位置l上的数移到后面某个位置，而位于[l+1,r]上的数都整体向前移动了一个位置，我们判断一个位置需不需要向后挪很简单，就是判断当前位置的数与后一个位置的数的大小关系，如果当前位置的数大于后一个位置的数那么我们当前位置就需要向后挪，具体挪到什么位置我们并不是很清楚，但是我们知道可以挪到后面的任意位置，我们可以先把这个数放入一个数组里面先存起来，继续上述过程，由于我们可以操作的次数是k，所以我们存起来的数不能超过k个，前面判断一个数需不需要移动其实就是一个单调栈，维护的是一个单调递减栈，但是当我们存入的元素等于k个了，那么后续的数就直接放入栈中，因为我们没办法继续为其排序了，已经在单调栈（由于k的限制，最终栈内的元素不一定是单调的）里面的我们存起来的数是相对顺序已经固定的了，但是数组中的数是可以插入到单调栈里面任意位置的，原则上是只能插入到他存入数组时的哪个位置之后的位置，但是由于栈是单调递减的，所以他也不会插入那个位置之前的位置，所以我们可以默认他保证字典序最大的情况下可以放置到任意位置，这样剩余的操作其实就是一个比较的过程，我们先对数组中元素进行从大到小排序，每次选择栈中一个元素和当前数组的元素进行比较，选择较大的数放入答案数组，直至所有的数都放入答案数组即可。

细节见代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=3e5+10;
int st[N],tt,a[N],b[N],tb,ans[N];
bool cmp(int a,int b)
{
	return a>b;
}
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n,m;
		scanf("%d%d",&n,&m);
		tt=tb=0;
		for(int i=1;i<=n;i++)
			scanf("%d",&a[i]);
		for(int i=1;i<=n;i++)
		{
			if(tb>=m)
			{
				st[++tt]=a[i];
				continue;
			}
			while(tt&&tb<=m&&st[tt]<a[i])
				b[++tb]=st[tt--];
			st[++tt]=a[i];
		}
		sort(b+1,b+tb+1,cmp);
		int i,j=1,k=1;
		for(i=0;i<=n;)
		{
			if(j>tt||k>tb) break;
			if(st[j]>=b[k]) ans[++i]=st[j++];
			else ans[++i]=b[k++];
		}
		while(j<=tt) ans[++i]=st[j++];
		while(k<=tb) ans[++i]=b[k++];
		printf("%d",ans[1]);
		for(int i=2;i<=n;i++)
			printf(" %d",ans[i]);
		puts("");
	}
	return 0;
}