View Code of Problem 134

#include <stdio.h>
//c语言解法，直接写了个快排 
typedef struct num{
	int data; //值 
	int pos;  //下标 
} infor;

infor arr[100001];

//利用快排 
int Partition(struct num arr[], int low, int high){
	int p1 = arr[low].data;
	int p2 = arr[low].pos;
	while(low<high){
		while(low<high && arr[high].data>=p1) high--;
		arr[low].data = arr[high].data;
		arr[low].pos = arr[high].pos;
		while(low<high && arr[low].data<=p1) low++;
		arr[high].data = arr[low].data;
		arr[high].pos = arr[low].pos;
	}
	arr[low].data = p1;
	arr[low].pos = p2;
	return low;
}
 
void QuickSort(struct num arr[], int low, int high){
	if(low<high){
		int pivot = Partition(arr, low, high);
		QuickSort(arr, low, pivot-1);
		QuickSort(arr, pivot+1, high);
	}
}
 
int main(){
	int n, q, l, r; 
	//输入1：1个整数n，n个整数，1<=n<=100000 
	while(scanf("%d", &n) != EOF){
		for(int i=1; i<=n; i++){
			scanf("%d", &arr[i].data);
			arr[i].pos = i;
		}
		//处理1：对数组进行快排，从小到大 
		QuickSort(arr, 1, n);
		//输入2：1个整数q，q对整数，1<=q<=100000，1<=l<=r<=n 
		scanf("%d", &q);
		while(q--){
			scanf("%d %d", &l, &r);
			//处理2：遍历数组，输出第一个符合区间的数 
			for(int i=1; i<=n; i++){
				if(l<=arr[i].pos && arr[i].pos<=r){
					//输出：q个整数
					printf("%d\n", arr[i].data);
					break;
				}
			}
			
		}
	}
}