E - Array Queries

线段树

题目大意

给定一个数组，查询给定区间内的最小值

解题思路

RMQ模板题

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <map>
#include <vector>
#include <cstring>
#include <cmath>
#include <set>
using namespace std;
const int N = 100100;
int dp[20][N], arr[N];
int cas;
void ST(int n)
{
    for(int i = 1; i <= n; i++)
        dp[0][i] = arr[i];
    for(int i = 1; (1<<i) <= n; i++)
        for(int j = 1; j <= n - (1<<i) + 1; j++)
            dp[i][j] = min(dp[i-1][j], dp[i-1][j+(1<<(i-1))]);
}
int RMQ(int l, int r)
{
    int k = log2(r - l + 1);
    return min(dp[k][l], dp[k][r-(1<<k)+1]);
}
int main()
{
    int t, n, m, a, b;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; i++)
            scanf("%d", arr + i);
        ST(n);
        printf("Case %d:\n", ++cas);
        for(int i = 0; i < m; i++)
        {
            scanf("%d%d", &a, &b);
            printf("%d\n", RMQ(a, b));
        }
    }
    return 0;
}