维护一个栈，实现下面的功能：
1、0操作和1操作交替存入栈；
2、0操作严格降序，1操作严格升序。
这就是全部的核心要点了。

栈维护好了，可以发现这是一个越来越小的区间，区间内的东西是有序的，区间外的东西是固定的，所以可以由外向内一个一个填值。

时间复杂度O(n+m)。
具体可以看看我写得挺烂的博客 蓝桥杯 双向排序题解
(c++代码在下面)

java代码：

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
public class Main
{
    public static void main(String[]args) throws IOException{
        int n=in();
        int m=in();
        int[]sta=new int[m];
        int cnt=0;
        while(m-->0){
            int op=in();
            int mid=in();
            {//维护栈
                if(op==0){
                    if(cnt%2!=op)//如果要放入的指令与栈中最后一个指令类型相同
                    {
                        if(cnt-1>=0&&sta[cnt-1]<=mid)cnt--;//则进行第一轮比较，如果当前更大则弹出最后一个
                        else continue;//否则直接舍去当前指令，进入下一层循环
                    }
                    while(cnt-2>=0&&sta[cnt-2]<=mid) cnt-=2;//循环弹出
                }else{
                    if(cnt%2!=op)//如果要放入的指令与栈中最后一个指令类型相同
                    {
                        if(cnt-1>=0&&sta[cnt-1]>=mid)cnt--;//则进行第一轮比较，如果当前更小则弹出最后一个
                        else continue;//否则直接舍去当前指令，进入下一层循环
                    }
                    while(cnt-2>=0&&sta[cnt-2]>=mid) cnt-=2;//循环弹出
                }
                sta[cnt++]=mid;//压入栈
            }
        }
        int l=1;
        int r=n;
        int[] ans=new int[n+1];
        //x从大到小，从外到内填数字
        int x=n;
        for(int i=0;i<cnt;i++){
            int mid=sta[i];
            if(i%2==1){
                mid=Math.min(r, mid);
                while(l<mid)ans[l++]=x--;
            }
            else {
                mid=Math.max(l, mid);
                while(r>mid)ans[r--]=x--;
            }
            if(r-l<1)break;
        }
        if(l<=r)
            if(cnt%2==1) {
                while(l<=r)ans[l++]=x--;
            }else {
                while(l<=r)ans[r--]=x--;
            }
        out.print(ans[1]);
        for(int i=2;i<=n;i++) {
            out.print(" "+ans[i]);
        }
        out.println();
        out.flush();
    }
    static StreamTokenizer in=new StreamTokenizer (new BufferedReader(new InputStreamReader(System.in)));
    static PrintWriter out=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    static int in() throws IOException{
        in.nextToken();
        return(int)in.nval;
    }
}

c++代码:

#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    int sta[m];//栈数组
    int cnt=0;//栈的长度
    while(m-->0)
    {
        int op;
        int mid;
        scanf("%d %d",&op,&mid);

        if(op==0){
            if(cnt%2!=op)
            {
                if(cnt-1>=0&&sta[cnt-1]<=mid)cnt--;
                else continue;
            }
            while(cnt-2>=0&&sta[cnt-2]<=mid){
                cnt-=2;
            }
        }else{
            if(cnt%2!=op)
            {
                if(cnt-1>=0&&sta[cnt-1]>=mid)cnt--;
                else continue;
            }
            while(cnt-2>=0&&sta[cnt-2]>=mid){
                cnt-=2;
            }
        }
        sta[cnt++]=mid;
    }
    int l=1;
    int r=n;
    int ans[n+1];//答案数组
    int x=n;
    for(int i=0;i<cnt;i++){
        int mid=sta[i];
        if(i%2==1){
            mid=min(r, mid);
            while(l<mid)ans[l++]=x--;
        }
        else {
            mid=max(l, mid);
            while(r>mid)ans[r--]=x--;
        }
        if(r-l<1)break;
    }
    if(l<=r)
        if(cnt%2==1) {
            while(l<=r)ans[l++]=x--;
        }else {
            while(l<=r)ans[r--]=x--;
        }

    printf("%d",ans[1]);
    for(int i=2;i<=n;i++)
    {
        printf(" %d",ans[i]);
    }
    printf("\n");
}