3946. K-th Number

You are working for Macrohard company in data structures department. After failing your previous task about key insertion you were asked to write a new data structure that would be able to return quickly k-th order statistics in the array segment.

That is, given an array a[1 ... n] of different integer numbers, your program must answer a series of questions Q(i, j, k) in the form: "What would be the k-th number in a[i ... j] segment, if this segment was sorted?"

For example, consider the array a = (1, 5, 2, 6, 3, 7, 4). Let the question be Q(2, 5, 3). The segment a[2 ... 5] is (5, 2, 6, 3). If we sort this segment, we get (2, 3, 5, 6), the third number is 5, and therefore the answer to the question is 5.

Input. The first line contains n – the size of the array, and m – the number of questions to answer (1 ≤ n ≤ 100000, 1 ≤ m ≤ 5000). The second line contains n different integer numbers not exceeding 10⁹ by their absolute values – the array for which the answers should be given.

The following m lines contain question descriptions, each description consists of three numbers: i, j and k (1 ≤ i ≤ j ≤ n, 1 ≤ k ≤ j – i + 1) and represents the question Q(i, j, k).

Output. For each question output the answer to it – the k-th number in sorted a[i ... j] segment.

Sample Input

7 3

1 5 2 6 3 7 4

2 5 3

4 4 1

1 7 3

Sample Output

5

6

3

РЕШЕНИЕ

структуры данных – дерево отрезков

Анализ алгоритма

Заведем в каждой вершине дерева отрезков дополнительный массив. Вершина, соответствующая фундаментальному отрезку [i; j], содержит в своем массиве отсортированный набор чисел a_i, …, a_j.

Пусть запрос Query(l, r, x) находит количество чисел из интервала [l, r], которые меньше x. Для этого разобьем этот интервал на множество фундаментальных отрезков, в каждом из которых совершим бинарный поиск, подсчитав число элементов, меньших x. Время запроса составит .

Ответ на запрос Q(i, j, k) будем искать бинарным поиском. Следует найти такое a_p из интервала [a_i, …, a_j], что Query(l, r, a_p) равно k – 1. То есть если a_p является k –ым элементов на отрезке [i; j], то количество чисел на этом отрезке, меньших a_p, равно k – 1. Принципиальным в этой задаче является то, что все входные числа разные. Таким образом запрос выполняется за .

Реализация алгоритма

#include <cstdio>

#include <vector>

#include <algorithm>

#define MAX 100010

using namespace std;

int i, j, k, n, m, l, r, x;

int a[MAX];

vector<vector<int> > SegTree;

void build(int Vertex, int LeftPos, int RightPos)

{

if (LeftPos == RightPos)

SegTree[Vertex].push_back(a[LeftPos]);

else

{

int Middle = (LeftPos + RightPos) / 2;

build (2*Vertex, LeftPos, Middle);

build (2*Vertex+1, Middle+1, RightPos);

SegTree[Vertex].resize(RightPos - LeftPos + 1);

merge(SegTree[2*Vertex].begin(),SegTree[2*Vertex].end(),SegTree[2*Vertex+1].begin(),SegTree[2*Vertex+1].end(),SegTree[Vertex].begin());

}

}

int Query(int Vertex, int LeftPos, int RightPos, int Left, int Right, int x)

{

if (Left > Right) return 0;

if ((LeftPos == Left) && (RightPos == Right))

return lower_bound(SegTree[Vertex].begin(),SegTree[Vertex].end(),x) – SegTree[Vertex].begin();

int Middle = (LeftPos + RightPos) / 2;

return Query(2*Vertex, LeftPos, Middle, Left, min(Middle,Right), x) +

Query(2*Vertex+1, Middle+1, RightPos, max(Left,Middle+1), Right, x);

}

int main(void)

{

scanf("%d %d",&n,&m);

for(i = 1; i <= n; i++)

scanf("%d",&a[i]);

SegTree.resize(4*n);

build(1,1,n);

sort(a+1,a+n+1);

while(m--)

{

scanf("%d %d %d",&i,&j,&k);

int ll = 1, rr = n;

while(rr - ll > 1)

{

int mid = (ll + rr) / 2;

if(Query(1,1,n,i,j,a[mid]) < k)

ll = mid;

else

rr = mid;

}

if(Query(1,1,n,i,j,a[ll]+1) >= k)

printf("%d\n",a[ll]);

else

printf("%d\n",a[rr]);

}

return 0;

}