蓝桥杯1458双向排序

这道题暴力解能拿60%的分数如果想要满分得用到线性树如果不熟练考场上很容易写错60%import java.util.Scanner; // 1:无需package // 2: 类名必须Main, 不可修改 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Main { public static void main(String[] args) throws IOException { BufferedReader brnew BufferedReader(new InputStreamReader(System.in)); String[] s br.readLine().split( ); int nInteger.parseInt(s[0]),mInteger.parseInt(s[1]); Integer num[]new Integer[n1]; for (int i1;in;i){ num[i]i; } for (int i0;im;i){ String[] s1 br.readLine().split( ); int pInteger.parseInt(s1[0]),qInteger.parseInt(s1[1]); if (p0){ Arrays.sort(num,1,q1,(a,b)-b-a); }else { Arrays.sort(num,q,n1); } } for (int i1;in;i){ System.out.print(num[i] ); } } }100%import java.io.IOException; import java.util.*; import java.io.*; class InputReader { private final static int BUF_SZ 65536; BufferedReader in; StringTokenizer tokenizer; public InputReader(InputStream in) { super(); this.in new BufferedReader(new InputStreamReader(in), BUF_SZ); tokenizer new StringTokenizer(); } private String next() { while (!tokenizer.hasMoreTokens()) { try { tokenizer new StringTokenizer(in.readLine()); } catch (IOException e) { throw new RuntimeException(e); } } return tokenizer.nextToken(); } public int nextInt() { return Integer.parseInt(next()); } } class Tree { public int l 0; public int r 0; public int sum 0; public int lazy -1; } public class Main { public static final int N 100010; public static int n; public static int m; public static int op; public static int pos; public static Tree[] tree new Tree[N 2]; public static void push_up(int rt) { tree[rt].sum tree[rt 1].sum tree[rt 1 | 1].sum; } public static void push_down(int rt) { int x tree[rt].lazy; if (x ! -1) { int len1 tree[rt 1].r - tree[rt 1].l 1; int len2 tree[rt 1 | 1].r - tree[rt 1 | 1].l 1; tree[rt 1].sum len1 * x; tree[rt 1 | 1].sum len2 * x; tree[rt 1].lazy tree[rt 1 | 1].lazy x; tree[rt].lazy -1; } } public static void build(int l, int r, int rt) { tree[rt].l l; tree[rt].r r; tree[rt].lazy -1; if (l r) { tree[rt].sum 1; return; } int mid l r 1; build(l, mid, rt 1); build(mid 1, r, rt 1 | 1); push_up(rt); } public static void update1(int L, int R, int rt, int cnt) { if (cnt 0) { return; } if (tree[rt].sum cnt) { tree[rt].sum tree[rt].lazy 0; return; } push_down(rt); if (cnt tree[rt 1].sum) { update1(L, R, rt 1, cnt); } else { update1(L, R, rt 1 | 1, cnt - tree[rt 1].sum); tree[rt 1].sum 0; tree[rt 1].lazy 0; } push_up(rt); } public static void update2(int L, int R, int rt, int cnt) { if (cnt 0) { return; } int l tree[rt].l; int r tree[rt].r; int len r - l 1; if (len - tree[rt].sum cnt) { tree[rt].sum len; tree[rt].lazy 1; return; } push_down(rt); int cnt1 tree[rt 1].r - tree[rt 1].l 1 - tree[rt 1].sum; if (cnt cnt1) { update2(L, R, rt 1, cnt); } else { update2(L, R, rt 1 | 1, cnt - cnt1); tree[rt 1].sum tree[rt 1].r - tree[rt 1].l 1; tree[rt 1].lazy 1; } push_up(rt); } public static int query(int L, int R, int rt) { int l tree[rt].l; int r tree[rt].r; if (L l r R) { return tree[rt].sum; } push_down(rt); int mid l r 1; int res 0; if (L mid) { res query(L, R, rt 1); } if (R mid) { res query(L, R, rt 1 | 1); } return res; } public static void main(String[] args) { for (int i 0; i (N 2); i) tree[i] new Tree(); InputReader cin new InputReader(System.in); n cin.nextInt(); m cin.nextInt(); build(1, n, 1); while ((m--) ! 0) { op cin.nextInt(); pos cin.nextInt(); if (op 0) { int cnt0 n - tree[1].sum; int cnt Math.max(0, pos - cnt0); update1(1, n, 1, cnt); } else { int cnt1 tree[1].sum; int cnt Math.max(0, n - pos 1 - cnt1); update2(1, n, 1, cnt); } } int vv1 0; int vv2 0; for (int i n; i 1; i--) { if (query(i, i, 1) 0) { System.out.print(i ); } } for (int i 1; i n; i) { if (query(i, i, 1) 1) { System.out.print(i ); } } System.out.println(); } }