题目链接
import java.util.*; public class Main { static int N = 100010; static CII stk[] = new CII[N]; static int a[] = new int[N]; static int top; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); while(m -- > 0) { int t = sc.nextInt(); int x = sc.nextInt(); if(t == 0) { while(top > 0 && stk[top].t == 0) x = Math.max(x, stk[top -- ].x); while(top >= 2 && stk[top - 1].x <= x) top -= 2; stk[ ++ top] = new CII(0, x); } else if(top != 0) { while(stk[top].t == 1) x = Math.min(x, stk[top -- ].x); while(top >= 2 && stk[top - 1].x >= x) top -= 2; stk[ ++ top] = new CII(1, x); } } int l = 1, r = n, k = n; for(int i = 1; i <= top; i ++ ) { int x = stk[i].x; if(stk[i].t == 0) { while(r > x && l <= r) a[r -- ] = k -- ; } else { while(l < x && l <= r) a[l ++ ] = k -- ; } if(l > r) break; } if(top % 2 == 1) while(l <= r) a[l ++ ] = k -- ; else while(l <= r) a[r -- ] = k -- ; for(int i = 1; i <= n; i ++ ) System.out.print(a[i] + " "); } static class CII { int t, x; public CII(int a, int b) { t = a; x = b; } } }