【栈】第十二届蓝桥杯省赛第一场C++ B组/研究生组《双向排序》（c++）

【题目描述】

给定序列 (a1,a2,⋅⋅⋅,an)=(1,2,⋅⋅⋅,n)，即 ai=i。

小蓝将对这个序列进行 m 次操作，每次可能是将 a1,a2,⋅⋅⋅,aqi 降序排列，或者将 aqi,aqi+1,⋅⋅⋅,an 升序排列。

请求出操作完成后的序列。

【输入格式】

输入的第一行包含两个整数 n,m，分别表示序列的长度和操作次数。

接下来 m 行描述对序列的操作，其中第 i 行包含两个整数 pi,qi 表示操作类型和参数。当 pi=0 时，表示将 a1,a2,⋅⋅⋅,aqi 降序排列；当 pi=1 时，表示将 aqi,aqi+1,⋅⋅⋅,an 升序排列。

【输出格式】

输出一行，包含 n 个整数，相邻的整数之间使用一个空格分隔，表示操作完成后的序列。

【数据范围】

对于 30% 的评测用例，n,m≤1000；
对于 60% 的评测用例，n,m≤5000；
对于所有评测用例，1≤n,m≤10的5次方，0≤pi≤1，1≤qi≤n。

【输入样例】

3 3
0 3
1 2
0 2

【输出样例】

3 1 2

【样例解释】

原数列为 (1,2,3)。

第 1 步后为 (3,2,1)。

第 2 步后为 (3,1,2)。

第 3 步后为 (3,1,2)。与第 2 步操作后相同，因为前两个数已经是降序了。

【代码】

#include <iostream>
#include <cstring>
#include <algorithm>#define x first
#define y secondusing namespace std;typedef pair<int, int> PII;const int N = 100010;int n, m;
PII stk[N];
int ans[N];int main()
{scanf("%d%d", &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 -- ;elsewhile (l < stk[i].y && l <= r) ans[l ++ ] = k -- ;if (l > r) break;}if (top % 2)while (l <= r) ans[l ++ ] = k -- ;elsewhile (l <= r) ans[r -- ] = k -- ;for (int i = 1; i <= n; i ++ )printf("%d ", ans[i]);return 0;
}