【栈】双向排序【蓝桥杯】

题目

3419. 双向排序 - AcWing题库

双向排序 - 蓝桥云课

---

给定序列 $(a_1, a_2, ··· , a_n) = (1, 2, · · · , n)$ ，即 $a_i = i$ 。

小蓝将对这个序列进行 $m$ 次操作，每次可能是将 $a_1, a_2, ··· , a_{q_i}$ 降序排列，或者将 $a_{q_i}, a_{q_i+1}, ··· , a_n$ 升序排列。

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

输入格式

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

接下来 $m$ 行描述对序列的操作，其中第 $i$ 行包含两个整数 $p_i, q_i$ 表示操作类型和参数。当 $p_i = 0$ 时，表示将 $a_1, a_2, ··· , a_{q_i}$ 降序排列；当 $p_i = 1$ 时，表示将 $a_{q_i}, a_{q_i+1}, ··· , a_n$ 升序排列。

输出格式

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

数据范围

对于 $30\%$ 的评测用例， $n, m ≤ 1000$ ；
对于 $60\%$ 的评测用例， $n, m ≤ 5000$ ；
对于所有评测用例， $1 ≤ n, m ≤ 10^5，0 ≤ p_i ≤ 1，1 ≤ q_i ≤ 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$ 步操作后相同，因为前两个数已经是降序了。

解题

方法一：栈

思路

y总的视频讲解：AcWing 3419. 双向排序（蓝桥杯C++ AB组辅导课）。

代码

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        in.nextToken();
        int m = (int) in.nval;
        List<int[]> stk = new ArrayList<>();
        while (m-- > 0) {
            in.nextToken();
            int p = (int) in.nval;
            in.nextToken();
            int q = (int) in.nval;
            if (p == 0) {
                while (!stk.isEmpty() && stk.get(stk.size() - 1)[0] == 0) q = Math.max(q, stk.remove(stk.size() - 1)[1]);
                while (stk.size() >= 2 && stk.get(stk.size() - 2)[1] <= q) {
                    stk.remove(stk.size() - 1);
                    stk.remove(stk.size() - 1);
                }
                stk.add(new int[]{0, q});
            } else if (!stk.isEmpty()) {
                while (!stk.isEmpty() && stk.get(stk.size() - 1)[0] == 1) q = Math.min(q, stk.remove(stk.size() - 1)[1]);
                while (stk.size() >= 2 && stk.get(stk.size() - 2)[1] >= q) {
                    stk.remove(stk.size() - 1);
                    stk.remove(stk.size() - 1);
                }
                stk.add(new int[]{1, q});
            }
        }
        int l = 1, r = n, k = n;
        int[] ans = new int[n + 1];
        for (int[] pr : stk) {
            if (pr[0] == 0) {
                while (r > pr[1] && l <= r) ans[r--] = k--; 
            } else {
                while (l < pr[1] && l <= r) ans[l++] = k--;
            }
            if (l > r) break;
        }
        if ((stk.size() & 1) == 0) {
            while (l <= r) ans[r--] = k--;
        } else {
            while (l <= r) ans[l++] = k--;
        }
        for (int i = 1; i <= n; ++i) {
            System.out.print(ans[i] + " ");
        }
    }
}