第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1 算法训练 区间k大数查询

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <stdio.h>  
 #include <stdlib.h>  
 int Split(int *data,int pre,int rear)  
 {  
     int value=data[pre];  
     while(pre<rear)  
     {  
         while(data[rear]>=value && pre<rear) rear--;  
         data[pre]=data[rear];  
         while(data[pre]<value && pre<rear) pre++;  
         data[rear]=data[pre];  
     }  
     data[pre]=value;  
     return pre;  
 }  
 //快速排序  
 void QuickSort(int *data,int pre,int rear,int k)  
 {  
     if(pre<=rear)  
     {  
         int mid=Split(data,pre,rear);  
         if(mid==k)  
         {  
             printf("%dn",data[mid]);  
         }  
         else if(mid>k)  
         {  
             QuickSort(data,pre,mid-1,k);  
         }  
         else  
         {  
             QuickSort(data,mid+1,rear,k);  
         }  
     }  
 }  
 void Copy(int *data,int n,int *temp)  
 {  
     int i;  
     for(i=0;i<n;i++)  
     {  
         temp[i]=data[i];  
     }  
 }  
 int main()  
 {  
     int i;  
     int n;  
     int m;  
     int *data;  
     scanf("%d",&n);  
     data=(int *)malloc(sizeof(int)*n);  
     for(i=0;i<n;i++)  
     {  
         scanf("%d",&data[i]);  
     }  
     scanf("%d",&m);  
     while(m)  
     {  
         int pre;  
         int rear;  
         int k;  
         int *temp=(int *)malloc(sizeof(int)*n);  
         scanf("%d%d%d",&pre,&rear,&k);  
         Copy(data,n,temp);  
         QuickSort(temp,pre-1,rear-1,rear-k);  
         m--;  
     }  
     return 0;  
 } 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<stdio.h>
#include<algorithm>
using namespace std;
#define N 10005

int n,m;
int a[N],tree[15][N],sum[15][N];

bool cmp(int x,int y)
{
	return x>y;
}

void build(int x,int L,int R)
{
	if(L==R)	return;
	int i;
	int mid=(L+R)>>1;
	int lp=L,rp=mid+1,l=mid-L+1;
	for(i=L;i<=R;i++)
		if(tree[x][i]>a[mid])
			l--;
	for(i=L;i<=R;i++)
	{
		sum[x][i]=i==L?0:sum[x][i-1];
		if(a[mid]==tree[x][i] && l)
		{
			l--;
			tree[x+1][lp++]=tree[x][i];
			sum[x][i]++;
		}
		else
		if(tree[x][i]>a[mid])
		{
			tree[x+1][lp++]=tree[x][i];
			sum[x][i]++;
		}
		else
			tree[x+1][rp++]=tree[x][i];
	}
	build(x+1,L,mid);
	build(x+1,mid+1,R);
}

int query(int x,int L,int R,int l,int r,int k)
{
	if(l==r)	return tree[x][l];
	int mid=(L+R)>>1;
	int t,tt;
	t=l==L?0:sum[x][l-1];
	tt=sum[x][r]-t;
	if(k<=tt)
		return query(x+1,L,mid,L+t,L+t+tt-1,k);
	else
		return query(x+1,mid+1,R,mid-L+1+l-t,mid-L+1+r-t-tt,k-tt);
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		tree[0][i]=a[i];
	}
	sort(a+1,a+1+n,cmp);
	build(0,1,n);
	scanf("%d",&m);
	int l,r,k;
	while(m--)
	{
		scanf("%d%d%d",&l,&r,&k);
		printf("%dn",query(0,1,n,l,r,k));
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try {
			int n = Integer.parseInt(br.readLine());
			int[] arr = new int[n+1];
			
			String[] s = br.readLine().split(" ");
			for (int i = 1; i < arr.length; i++) {
				arr[i] = Integer.parseInt(s[i-1]);
			}
			int m = Integer.parseInt(br.readLine());
			String[] s1;
			int[][] brr = new int[m][3];
			for (int i = 0; i < m; i++) {
				s1 = br.readLine().split(" ");
				for (int j = 0; j < s1.length; j++) {
					brr[i][j] = Integer.parseInt(s1[j]);
				}
			}
			int a;
			int b;
			int c;
			for (int i = 0; i < m; i++) {
				a = brr[i][0];
				b = brr[i][1];
				c = brr[i][2] - 1;
				int[] brr1 = new int[b - a + 1];
				System.arraycopy(arr, a, brr1, 0, b - a + 1);
				shellSort(brr1);
				System.out.println(brr1[b - a - c]);
			}
		} catch (IOException e) {
			e.printStackTrace();
		}finally {
			try {
				br.close();
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
	}
	
	public static void shellSort(int[] arr) {
	    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
	        for (int i = gap; i < arr.length; i++) {
	            int j = i; 
	            int temp = arr[j]; 
	            if (arr[j] < arr[j - gap]) {
	                while (j - gap >= 0 && temp < arr[j - gap]) {
	                    arr[j] = arr[j - gap];
	                    j -= gap; 
	                }
	                arr[j] = temp;
	            }
	        }
	    }
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
n = input()
n_list = list(map(int,input().split()))
m = int(input())
Ls = []
for i in range(m):
    Ls.append(list(map(int,input().split())))
for j in Ls:
    l=int(j[0])-1
    r=int(j[1])
    k=int(j[2])- 1
    result = sorted(n_list[l:r],reverse=True)
    print(result[k])