双向排序（参照acwing的yxc）

双向排序给定序列 (a1,a2,⋅⋅⋅,an)(1,2,⋅⋅⋅,n)即 aii。小蓝将对这个序列进行 m 次操作每次可能是将 a1,a2,⋅⋅⋅,aqi 降序排列或者将 aqi,aqi1,⋅⋅⋅,an 升序排列。请求出操作完成后的序列。输入格式输入的第一行包含两个整数 n,m分别表示序列的长度和操作次数。接下来 m 行描述对序列的操作其中第 i 行包含两个整数 pi,qi 表示操作类型和参数。当 pi0 时表示将 a1,a2,⋅⋅⋅,aqi 降序排列当 pi1 时表示将 aqi,aqi1,⋅⋅⋅,an 升序排列。输出格式输出一行包含 n 个整数相邻的整数之间使用一个空格分隔表示操作完成后的序列。数据范围对于 30% 的评测用例n,m≤1000对于 60% 的评测用例n,m≤5000对于所有评测用例1≤n,m≤1050≤pi≤11≤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(idx0node[idx].pefix1){ if(openode[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(idx0node[idx].pefix0){ if(node[idx].opeope)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 lr; i) { if (node[i].pefix 0) { while (r node[i].ope lr) { res[r--] k--; } } else { while (l node[i].ope lr) { 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; } } }