双向排序（参照acwing的yxc）
双向排序
给定序列 (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≤105，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 步操作后相同，因为前两个数已经是降序了。
代码：
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int N = 100010; static Node[] node = new Node[N]; static int[] res = new int[N]; public static void main(String[] args) throws IOException { //qq BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] g = br.readLine().split(" "); int n = Integer.parseInt(g[0]), m = Integer.parseInt(g[1]); int idx = 0; for (int i = 0; i < m; i++) { g = br.readLine().split(" "); int pefix = Integer.parseInt(g[0]), ope = Integer.parseInt(g[1]); // 第一个操作必须是前缀，跳过起始的后缀 if (idx == 0 && pefix == 1) continue; if (pefix == 0) { // 合并连续的前缀操作，取最大值 if (idx != 0 && node[idx].pefix == 0) { ope = Math.max(ope, node[idx].ope); idx--; } if(idx>0&&node[idx].pefix==1){ if(ope<node[idx].ope)continue; } // 检查是否能覆盖前一对操作 while (idx >= 2 && node[idx - 1].ope < ope) { idx -= 2; } // 压入当前操作 node[++idx] = new Node(pefix, ope); } else { // 合并连续的后缀操作，取最小值 if(idx > 0 && node[idx].pefix == 1) { ope = Math.min(ope, node[idx].ope); idx--; } if(idx>0&&node[idx].pefix==0){ if(node[idx].ope<ope)continue; } // 检查是否能覆盖前一对操作 while (idx >= 2 && node[idx - 1].ope > ope) { idx -= 2; } // 压入当前操作 node[++idx] = new Node(pefix, ope); } } int k = n, l = 1, r = n; // 按照栈中的操作序列填充数组 for (int i = 1; i <= idx && l<=r; i++) { if (node[i].pefix == 0) { while (r > node[i].ope && l<=r) { res[r--] = k--; } } else { while (l < node[i].ope && l<=r) { res[l++] = k--; } } } // 填充剩余区间 if (idx % 2 == 1) { while (l <= r) res[l++] = k--; } else { while (l <= r) res[r--] = k--; } StringBuilder sb = new StringBuilder(); for (int i = 1; i <= n; i++) { sb.append(res[i]).append(" "); } System.out.println(sb.toString().trim()); } static class Node { int pefix; int ope; public Node() {} public Node(int pefix, int ope) { this.pefix = pefix; this.ope = ope; } } }