题目描述

YPZ打算毕业进厂拧螺丝。工作是管理流水线。流水线可以抽象化类似一个双端队列（不知道为什么），相比普通的队列只能从尾部插入元素，双端队列还能从队列的头部插入元素。例如，给出一个入队序列p = [4, 2, 3, 1]，其中一个可能的操作序列如下：

在双端队列的头部加入4，双端队列序列为[4]；

在双端队列的头部加入2，双端队列序列为[2, 4]；

在双端队列的尾部加入3，双端队列序列为[2, 4, 3]；

在双端队列的头部加入1，双端队列序列为[1, 2, 4, 3]；

现在YPZ要对流水线进行入队操作，每个产品都有价值x,请你找到在流水线中按价值字典顺序排列最小的序列。

输入格式

第一行包含一个整数t （1 <= t <= 1000）测试用例组数。

每组测试的第一行包含一个整数n（1 <= n <= 2×10^5）给出流水线的长度。

每组测试的第二行包含n个整数的流水线序列，其中从1到n的每个整数只出现一次，分别代表某个产品的价值。

//利用双链表实现天梯赛选拔：L2-排队进厂 问题

#include<iostream>
#include<string>
#include<cstdio>
using namespace std;

const int N=100010;
int val[N],l[N],r[N],idex=2;//*默认0为左头节点，1为右头节点

void insert_l(int x){
    l[idex]=0;
    r[idex]=r[0];
    val[idex]=x;
    l[r[0]]=idex;
    r[0]=idex++;
}

void insert_r(int x){
    r[idex]=1;
    l[idex]=l[1];
    val[idex]=x;
    r[l[1]]=idex;
    l[1]=idex++;
}

void delet(int k){
    k+=1;//**由于插入数的下标是从2开始的，所以在用到第几次插入的值是，应在原值上加1
    r[l[k]]=r[k];
    l[r[k]]=l[k];
}

void insert_kl(int k,int x){
    k+=1;//**
    val[idex]=x;
    l[idex]=l[k];
    r[l[k]]=idex;
    r[idex]=k;
    l[k]=idex++;
}

void insert_kr(int k,int x){
    k+=1;//**
    val[idex]=x;
    r[idex]=r[k];
    l[r[k]]=idex;
    l[idex]=k;
    r[k]=idex++;
}

int main(){

    int m;
    cin>>m;
    while(m--){
        r[0]=1;
        l[1]=0;//*
        int n;
        scanf("%d",&n);
        while(n--){
            int t;
            cin>>t;
            if(t<=val[r[0]])        
                insert_l(t);
            else
                insert_r(t);
        }
        for(int i=r[0];i!=1;i=r[i]) printf("%d ",val[i]);
        printf("\n");
    }

    return 0;
}