（codeforce631）C.Report（单调栈）

题目链接：Problem - 631C - Codeforces

样例输入：

3 1
1 2 3
2 2

样例输出：

2 1 3 

题意：给定一个长度为n的数组，然后给出m次操作

操作的格式：

1 r，将子序列a[1]~a[r]从小到大排序

2 r，将子序列a[1]~a[r]从大到小排序

让我们输出操作后的序列，注意是多组样例

分析：我们先来看一下这些操作具有什么特点：
假如我们现在先对前7个元素升序，再对前10个元素降序，那么我们还有必要对前7个元素进行升序处理吗？其实显然是没必要的，因为当后面的操作范围比当前操作范围大时，当前操作一定会被操作范围更大的操作直接修改，所以这也就给了我们一个启发，有效操作的范围一定是越来越小的，有效操作是指当前操作后面没有比当前操作范围更大的操作，这个显然可以用单调栈直接处理出来，然后我们的有效操作范围就是一个单调递减的序列，但是我们再来思考一个问题，假如两个有效操作是相同性质的，也就是说当两个相邻的操作都是升序或者降序的时候，由于后面的操作的范围更小，所以后面的操作就没有什么实质的意义，我们也可以把这种操作给清除掉，那么剩下的有效操作就是满足下面两个性质的操作了：

1.操作范围逐渐减小

2.相邻两个操作一定是一个升序一个降序

有了这些操作我们来分析一下应该怎么进行操作来得到最终的序列

首先最大操作范围都没操作到的部分就是原序列对应的数，我们对剩余的数进行从小到大排序，如果当前操作是一个升序操作，说明上一个操作是一个降序操作，那么假如当前操作的范围是r1，上一个操作的范围是r2，那么有r2>r1，经过上一次操作完就是一个降序序列了，那么当前操作无法覆盖的那些范围的数就已经固定了，不可能再被后续操作更新到了，所以我们可以从小到大排序后的序列中从前往后选取一些数填到对应的当前操作覆盖不到的区域上，同理假如当前操作是一个降序操作而上一个操作是一个升序操作，我们就可以从小到大排序后的序列中从后往前选取一些数填到对应的当前操作覆盖不到的区域上，这个过程我们可以用双指针操作一下，这样整个题目的复杂度就就是O（n）了，可能细节比较多，大家可以好好看看代码。

下面是代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int N=2e5+10;
int r[N],op[N],a[N],ans[N];
int st[N],tt;
int main()
{
	int n,m;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		for(int i=1;i<=n;i++)
			scanf("%d",&a[i]);
		for(int i=1;i<=m;i++)
		    scanf("%d%d",&op[i],&r[i]);
		tt=0;
		for(int i=1;i<=m;i++)
		{
			while(tt&&r[st[tt]]<=r[i]) tt--;//用单调栈处理一下有效操作 
			if(!tt) st[++tt]=i;
			else if(op[st[tt]]!=op[i]) st[++tt]=i;//当两者做的是相同性质的排序时就没必要做了 
		}
		for(int i=r[st[1]]+1;i<=n;i++) 
			ans[i]=a[i];
		sort(a+1,a+r[st[1]]+1);
		int ll=1,rr=r[st[1]];
		r[st[tt+1]]=0;
		if(op[st[tt]]==1) op[st[++tt]]=2;
		else op[st[++tt]]=1;
		for(int i=2;i<=tt;i++)
		{
			if(op[st[i]]==1)//当前按照升序排列
				for(int j=r[st[i-1]];j>r[st[i]];j--) 
					 ans[j]=a[ll++];//就从小到大取一些数 
			else
				for(int j=r[st[i-1]];j>r[st[i]];j--)
					 ans[j]=a[rr--];
		}
		for(int i=1;i<=n;i++)
			printf("%d ",ans[i]);
		puts("");
	}
	return 0;
}