52 lines
1.9 KiB
C++
52 lines
1.9 KiB
C++
// lanqiao 1458 双向排序(栈优化)
|
||
#include<bits/stdc++.h>
|
||
using namespace std;
|
||
/*
|
||
题意:
|
||
该题目首先给定了一个升序序列，通过两种操作(前缀降序和后缀升序)对序列进行处理最后得到一个结果序列
|
||
通过分析题目可以得到以下性质:
|
||
1.连续的前缀操作和后缀操作，只需要暴力最长区间对应操作即可，其余操作均属于无效操作
|
||
2.对于左右交替的有效操作，可以使用线段树或者Splay树处理交集区间的翻转
|
||
由于在左右交替的过程中，交集区间不断缩小，所以也可以从开到和结尾处朝着中间填数
|
||
*/
|
||
const int N = 1e5 + 10;
|
||
pair<int, int> stk[N]; // 栈记录有效操作
|
||
int s[N], top; // 记录栈顶
|
||
int main(){
|
||
int n, m; cin >> n >> m;
|
||
while(m--){
|
||
int p, q; cin >> p >> q;
|
||
if(p == 0){ // 前缀降序
|
||
// 处理连续的前缀降序操作, 保留最长区间的有效操作
|
||
while(top&&stk[top].first == 0) q = max(q, stk[top--].second);
|
||
while(top >= 2 && stk[top-1].second <= q) top -= 2; // 维持交错的单调性
|
||
stk[++top] = {0, q}; // 将当前操作入栈
|
||
}else if(top){ // 后缀升序
|
||
while(top&&stk[top].first == 1) q = min(q, stk[top--].second);
|
||
while(top>=2&&stk[top-1].second >= q) top -= 2;
|
||
stk[++top] = {1, q};
|
||
}
|
||
}
|
||
int l = 1, r = n, k = n;
|
||
for(int i = 1; i <= top; i++){
|
||
if(stk[i].first){
|
||
while(l < stk[i].second && l < r) s[l++] = k--; // 升序从左侧开始填充
|
||
}else{
|
||
while(r > stk[i].second && l < r) s[r--] = k--; // 降序从右侧开始填充
|
||
}
|
||
}
|
||
// 最后补充未填充的数字
|
||
if(top % 2){
|
||
while(l <= r) s[l++] = k--;
|
||
}else{
|
||
while(l <= r) s[r--] = k--;
|
||
}
|
||
for(int i = 1; i <= n; i++) cout << s[i] << " ";
|
||
return 0;
|
||
}
|
||
/* test samples 3 1 2
|
||
3 3
|
||
0 3
|
||
1 2
|
||
0 2
|
||
*/ |