AcWing 3419. 双向排序
原题链接
困难
作者:
Moonlight
,
2021-05-25 11:05:09
,
所有人可见
,
阅读 589
C++ 代码
#include <algorithm>
#include <iostream>
#include <cstring>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 100010;
int n, m;
PII stk[N];
int ans[N];
int main(void){
cin >> n >> m;
int top = 0;
while(m --){
int p, q;
scanf("%d%d",&p, &q);
if(!p){ //前缀操作
//两个连续的左操作
while(top && stk[top].x == 0) q = max(q, stk[top --].y);
//删掉前边比当前操作小的左端操作及其对应的右端操作
while(top >= 2 && stk[top - 1].y <= q) top -= 2;
stk[++ top] = {0, q};
}
else if(top){ //当第一个操作为右端操作时,没有必要处理
while(top && stk[top].x == 1) q = min(q, stk[top --].y);
while(top >= 2 && stk[top - 1].y >= q) top -= 2;
stk[++ top] = {1, q};
}
}
int k = n, l = 1, r = n;
//从前往后遍历所有操作
for(int i = 1; i <= top; i ++){
//第一个操作为前缀降序操作,该区间右端的数是可以固定的了。
if(stk[i].x == 0)
while(r > stk[i].y && l <= r) ans[r --] = k --;
else
while(l < stk[i].y && l <= r) ans[l ++] = k --;
if(l > r) break;
}
if(top % 2){ //做完了右区间,还剩一个左区间。
//剩下的左区间操作为降序,我们从左边开始填。
while(l <= r) ans[l ++] = k --;
} else{
while(l <= r) ans[r --] = k --;
}
for(int i = 1; i <= n; i ++){
printf("%d ", ans[i]);
}
return 0;
}