传送门

题目大意

给出一个长度为 n n n 的序列 a a a，并且有 m m m 个操作，每个操作包含一个 t i t_i ti​ 和 r i r_i ri​。若 t i = 1 t_i=1 ti​=1，则将 a a a 中前 r i r_i ri​ 个从小到大排序。若 t i = 2 t_i=2 ti​=2，则将 a a a 中的前 r i r_i ri​ 个从大到小排序。

求最终的序列 a a a。

Solution

首先有一个显而易见的结论，如果某个操作之后有一个 r r r 大于等于该操作，那么当前操作相当于白给，因为之后会被覆盖。（这与 t t t 无瓜）

因此，我们总是可以将任意序列转化成一个 r r r 单调降序的序列。这个只要用单调栈维护就可以了，这里不再赘述，复杂度 O ( n ) O(n) O(n)。

然后考虑任意相邻的两个操作 o p i op_i opi​ 和 o p i + 1 op_{i+1} opi+1​。显然，前者的 r r r 一定是大于后者的，那么在它们之间的区间内，其单调性必然是依赖于 o p i op_i opi​ 的 t t t 的。就可以用优先队列维护。

这么说比较抽象，所以来看图吧。

每次操作我们只需要维护右图中黑色部分就可以了，显然，这部分就是整段的最大部分，而要维护最大还是最小是与操作的 t t t 相关的。比如上图就是给出了 o p i op_i opi​ 的 t t t 是 1 1 1 而 o p i + 1 op_{i+1} opi+1​ 的 t t t 是 2 2 2 的情况。

因此需要一个大根堆和小根堆来维护。

Code

#include<bits/stdc++.h>
#define ll long long
#define inf 1<<30
#define INF 1ll<<60
using namespace std;
int read(){
	int w=0,f=1; char c=getchar();
	while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9'){w=w*10+c-'0';c=getchar();}
	return w*f;
}
const int MAXN=2e5+10;
struct node{
	int t,r;
	void input(){
		t=read();r=read();
	}
}stk[MAXN];
int top,a[MAXN];
priority_queue<int> ge;
priority_queue<int,vector<int>,greater<int> > le;
int main()
{
	int n=read(),m=read();
	for(int i=1;i<=n;i++)
		a[i]=read();
	for(int i=1;i<=m;i++){
		node tmp;tmp.input();
		while(top&&stk[top].r<=tmp.r) top--;
		stk[++top]=tmp;//单调栈维护严格下降序列
	}
	for(int i=1;i<=stk[1].r;i++)
		le.push(a[i]),ge.push(a[i]);//由于只有前最大的 r 个数会参与，所以优先队列只存前 stk[1].r 个
	int p=stk[1].r;
	stk[top+1].r=0;
	for(int i=1;i<=top;i++){
		int T=stk[i].r-stk[i+1].r;
		while(T--){
			if(stk[i].t==1)
				a[p]=ge.top(),ge.pop();//选取最大的填入
			else a[p]=le.top(),le.pop();
			p--;
		}
	}
	for(int i=1;i<=n;i++) printf("%d ",a[i]);
	return 0;
}