题目描述

blablabla

算法1

Java 代码

import java.io.*;
import java.util.Scanner;

public class Main {
    private static int N = 100010;
    private static int[] e = new int[N];
    private static int[] l = new int[N];  // left node index
    private static int[] r = new int[N];  // right node index
    private static int idx;

    private static void init() {
       idx = 2;
       l[1] = 0;
       r[0] = 1;
    } 

    private static void add(int k, int val){
        e[idx] = val;       // set value
        r[idx] = r[k];      // point new idx right to origin k right node
        l[idx]=l[r[k]];     // point new idx left to origin k left node.
        l[r[k]] = idx;      // point orign k left node to new idx
        r[k] = idx;         // point origi k right node to new idx
        idx++;
    }

    private static void remove(int k){
        r[l[k]] = r[k];
        l[r[k]] = l[k];
    }


    public static void main(String[] args) throws IOException {
        Scanner sc=new Scanner(System.in);
        int m=sc.nextInt();
        init();
        while (m-- > 0) {
            String c=sc.next();
            int k,x;
            if(c.equals("L")){
                x = sc.nextInt();
                add(0,x);
            }else if(c.equals("R")){
                x = sc.nextInt();
                add(l[1],x);
            }else if(c.equals("D")){
                k = sc.nextInt();
                remove(k+1);
            }else if(c.equals("IL")){
                k = sc.nextInt();
                x = sc.nextInt();
                add(l[k+1],x);
            }else if(c.equals("IR")){
                k = sc.nextInt();
                x = sc.nextInt();
                add(k+1,x);
            }
        }

        for(int i=0;r[i]!=1;i=r[i]){
            System.out.print(e[r[i]]+" ");
        }
    }
}