[数据结构与算法]12届蓝桥杯省赛Java B组 双向排序

给定序列 (a1,a2,???,an)=(1,2,???,n)，即 ai=i。

小蓝将对这个序列进行 m 次操作，每次可能是将 a1,a2,???,aqi 降序排列，或者将 aqi,aqi+1,???,an 升序排列。

请求出操作完成后的序列。

输入格式
输入的第一行包含两个整数 n,m，分别表示序列的长度和操作次数。

接下来 m 行描述对序列的操作，其中第 i 行包含两个整数 pi,qi 表示操作类型和参数。当 pi=0 时，表示将 a1,a2,???,aqi 降序排列；当 pi=1 时，表示将 aqi,aqi+1,???,an 升序排列。

输出格式
输出一行，包含 n 个整数，相邻的整数之间使用一个空格分隔，表示操作完成后的序列。

数据范围
对于 30% 的评测用例，n,m≤1000；
对于 60% 的评测用例，n,m≤5000；
对于所有评测用例，1≤n,m≤10^5，0≤pi≤1，1≤qi≤n。

import java.util.Scanner;
//1:无需package
//2: 类名必须Main, 不可修改

public class Main {
	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		int n,m;
		
		n=in.nextInt();m=in.nextInt();
		int[] a=new int[n+1];
		for(int i=1;i<=n;i++)a[i]=i;
		for(int i=0;i<m;i++) {
			int x,y;
			x=in.nextInt();y=in.nextInt();
			if(x==0) {
				down(a,1,y);
			}
			if(x==1) {
				up(a,y,n);
			}
		}
		for(int i=1;i<n+1;i++) {
			System.out.print(a[i]+" ");
		}
	}
	public static void up(int[] K,int s,int t) {
		int i,j;
		int temp;
		if(s<t){
			i=s;
			j=t+1;
			while(true){
			do{
				i++;
			}while(K[i]<K[s]&&i!=t);
			do{
				j--;
			}while(K[j]>K[s]&&j!=s);
			if(i<j){
				temp=K[i];
				K[i]=K[j];
				K[j]=temp;
			}
			else break;	
			}
			temp=K[s];
			K[s]=K[j];
			K[j]=temp;
			up(K,s,j-1);
			up(K,j+1,t);
		}
	}
	public static void down(int[] K,int s,int t) {
		int i,j,temp;
		if(s<t) {
			i=s;
			j=t+1;
			while(true) {
				do {
					j--;
				}while(K[j]<K[s]&&j!=s);
				do {
					i++;
				}while(K[i]>K[s]&&i!=t);
				if(i<j){
					temp=K[i];
					K[i]=K[j];
					K[j]=temp;
				}
				else break;	
			}
			temp=K[j];
			K[j]=K[s];
			K[s]=temp;
			down(K,s,j-1);
			down(K,j+1,t);
		}
	}
}

练习系统得分30，剩下超时，用的快速排序，想不通了，求一个满分算法···