陕西网络推广介绍网站内部链接优化
【题目描述】
给定序列 (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;
}