11772. Negative Score

Orianna is a great swimmer and she's going to a swimming competition this month and needs your help as she is highly paranoic about the results of the competition.

The competition consists in some sort of evaluations, every judge makes a score and, based on that score and the score of other contestants she will get a score belonging to her results, those scores are final, meaning that will not change in the competition.

Orianna requires this solution with urgency, she is getting evaluated on a lot of ways and she is very worried about her results, so she wants to know what is the worst score from an evaluation A to other evaluation B inclusive.

Input. The first line will start with an integer t (1 ≤ t ≤ 100) representing the t test cases, then, t cases will follow, each of the cases starts with two integers n and q (1 ≤ n, q ≤ 10⁵), denoting the number of evaluations Orianna had, then, n integers will follow denoting the score on each evaluation (from -10⁹ to 10⁹), after that, q queries will begin, each query consist on two integers A and B (1 ≤ A ≤ B ≤ n).

Output. You must output the string “Scenario #i:“, a blank line and then the result of each query, remember, Orianna is interested on the worst score from evaluation A to evaluation B inclusive.

Sample Input

2

5 3

1 2 3 4 5

1 5

1 3

2 4

5 3

1 -2 -4 3 -5

1 5

1 3

2 4

Sample Output

Scenario #1:

1

1

2

Scenario #2:

-5

-4

-4

РЕШЕНИЕ

структуры данных – RMQ

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

В задаче следует реализовать запросы минимума на отрезках. При этом сам массив чисел остается статическим. Реализуем структуру данных RMQ.

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

#include <cstdio>

#include <cmath>

#include <vector>

#define MAX 100010

#define LOGMAX 17

using namespace std;

int mas[MAX][LOGMAX], arr[MAX];

int t, tests, n, i, q, a, b;

void Build_RMQ_Array(int *b)

{

int i, j;

for (i = 1; i <= n; i++) mas[i][0] = b[i];

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

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

if (mas[i][j - 1] < mas[i + (1 << (j - 1))][j - 1])

mas[i][j] = mas[i][j - 1];

else mas[i][j] = mas[i + (1 << (j - 1))][j - 1];

}

int RMQ(int i, int j)

{

int k = (int)(log(1.0 * j - i + 1) / log(2.0));

int res = mas[i][k];

if (mas[j - (1<<k) + 1][k] < res) res = mas[j - (1<<k) + 1][k];

return res;

}

int main(void)

{

scanf("%d",&tests);

for(t = 1; t <= tests; t++)

{

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

for(i = 1; i <= n; i++) scanf("%d",&arr[i]);

Build_RMQ_Array(arr);

printf("Scenario #%d:\n\n",t);

for(i = 0; i < q; i++)

{

scanf("%d %d",&a,&b);

printf("%d\n",RMQ(a,b));

}

}

return 0;

}

Реализация при помощи дерева отрезков

#include <cstdio>

#include <algorithm>

#define MAX 100010

#define INF 2100000000

using namespace std;

int SegTree[4*MAX] = {0};

int i, n, tests, t, q, a, b;

int mas[MAX];

void BuildTree(int *a, int v, int Left, int Right)

{

if (Left == Right)

SegTree[v] = a[Left];

else

{

int Middle = (Left + Right) / 2;

BuildTree(a, v*2, Left, Middle);

BuildTree(a, v*2+1, Middle+1, Right);

SegTree[v] = min(SegTree[v*2],SegTree[v*2+1]);

}

}

int GetMin(int v, int LeftPos, int RightPos, int Left, int Right)

{

if (Left > Right) return INF;

if ((Left == LeftPos) && (Right == RightPos)) return SegTree[v];

int Middle = (LeftPos + RightPos) / 2;

return min(GetMin(v*2, LeftPos, Middle, Left, min(Right,Middle)),

GetMin(v*2+1, Middle+1, RightPos, max(Left,Middle+1), Right));

}

int main(void)

{

scanf("%d",&tests);

for(t = 1; t <= tests; t++)

{

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

for(i = 1; i <= n; i++) scanf("%d",&mas[i]);

BuildTree(mas,1,1,n);

printf("Scenario #%d:\n\n",t);

for(i = 0; i < q; i++)

{

scanf("%d %d",&a,&b);

printf("%d\n",GetMin(1,1,n,a,b));

}

}

return 0;

}