题意：
百度。
思路：
如果该查询的R比前面的所有都大，那么前面所有都失效。
那么我先预处理出这些有效的。
那最坏的情况不就是栈里面元素（R）很多
n,n-1,n-2,n-3,n-4而且都是相反排序的。。。
总不能每次都那样循环一下，跟着他变吧。
所以找特性：
如果有序列132456
我的栈是
1 6
2 5
1 3
2 2
那么第一步从sort完：123456，那么这个a[6]=6肯定是确定了对吧。
继续看 2 5：我们能确定 a[5]=1,a[4]=2 对吧
继续看1 3 ：我们能确定a[3]=5。
继续看2 2：我们能确定a[2]=3,a[1]=4.
最后输出。这样我觉得仔细自己想想就能瞎搞出来了！自己想出来的方法才有乐趣啊~
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N=2e5+10;
struct asd{
int flag;
int R;
}e[N];
stack<asd>q;
int a[N],b[N][2];
int tp[N];
bool cmp(int x,int y)
{
return x>y;
}
int main()
{
asd now,nex;
int n,t;
scanf("%d%d",&n,&t);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=t;i++)
scanf("%d%d",&e[i].flag,&e[i].R);
for(int i=1;i<=t;i++)
{
while(!q.empty()&&q.top().R<e[i].R)
q.pop();
if(!q.empty()&&e[i].flag==q.top().flag)
continue;
q.push(e[i]);
}
int num=0;
while(!q.empty())
{
num++;
b[num][0]=q.top().flag;b[num][1]=q.top().R;
q.pop();
}
if(b[num][0]==1)
sort(a+1,a+b[num][1]+1);
else
sort(a+1,a+b[num][1]+1,cmp);
if(num==1)
{
for(int i=1;i<=n;i++)
printf("%d ",a[i]);
return 0;
}
int ii=n,jj=1,ij=n;
int s=1;
for(;ij>b[num][1];ij--,ii--)
tp[ij]=a[ij];
for(int i=num;i>=2;i--)
{
int cnt=b[i][1]-b[i-1][1];
if(s%2==0)
for(int p=1;p<=cnt;p++,ij--,jj++)
tp[ij]=a[jj];
else
for(int p=1;p<=cnt;p++,ij--,ii--)
tp[ij]=a[ii];
s++;
}
if(s%2==0)
for(int p=1;p<=b[1][1];p++,ij--,jj++)
tp[ij]=a[jj];
else
for(int p=1;p<=b[1][1];p++,ij--,ii--)
tp[ij]=a[ii];
for(int i=1;i<=n;i++)
printf("%d ",tp[i]);
return 0;
}
/*
6 4
1 3 4 5 2 6
1 6
2 5
1 3
2 2
*/