Обновить значение по заданному индексу, а также найти K-й наименьший элемент в том же запросе

Question

Дан массив (индексирование начинается с 1) размера S, а количество запросов N задается пользователем N (i) = (MPR); 1 <= я <= N. Выведите R-й минимальный элемент из массива после обновления M-го индекса. Пример: - Массив: [2, 4, 6, 1, 7], S = 5 </p>

Запросы: N = 3

2 5 3

5 3 2

4 8 4

Вывод: - 5 2 6

Answer 1

Вы можете ответить на каждый запрос за время O (logn). Идея состоит в том, чтобы использовать дерево сортировки слиянием . Эта структура данных позволяет O (logn) на обновление и O (log ² n) на запрос. Вы даже можете достичь O (logn) на запрос и обновление, используя структуры данных на основе политик g cc .

Answer 2

import java.util.*;
import java.io.*;
public class Solution{
    public static void main(String[] args)
    {
        Scanner sc=new Scanner(System.in);
        int S=sc.nextInt();
        int[] arr=new int[S];
        for(int i=0;i<S;i++)
        arr[i]=sc.nextInt();
        int Q=sc.nextInt();
        while(Q>0)
        {
            int M=sc.nextInt();
            int P=sc.nextInt();
            int R=sc.nextInt();
            int[] temp=arr;
            temp[M-1]=P;
            PriorityQueue<Integer> pq=new PriorityQueue<>(Collections.reverseOrder());
            for(int i=0;i<S;i++)
            {
                pq.add(temp[i]);
                if(pq.size()>R)
                pq.poll();
            }
            System.out.println(pq.peek());
            Q--;
        }
    }
}