Light oj 1082 - Array Queries（区间最小值）

#include <stdio.h>
#include <algorithm>
using namespace std;
const int maxn = 100010;

struct node
{
    int l, r, mid, minn;
}tree[maxn<<2];
int a[maxn];

void build(int l, int r, int o)
{
    tree[o].l = l;
    tree[o].r = r;
    int m = (l+r) >> 1;
    tree[o].mid = m;
    if (l == r)
    {
        tree[o].minn = a[l];
        return ;
    }
    build(l, m, o<<1);
    build(m+1, r, (o<<1)+1);
    tree[o].minn = min(tree[o<<1].minn, tree[(o<<1)+1].minn);
}

int query(int l, int r, int o)
{
    if (tree[o].l == l && tree[o].r == r)
        return tree[o].minn;
    if (r <= tree[o].mid)
        return query(l, r, o<<1);
    else if (l > tree[o].mid)
        return query(l, r, (o<<1)+1);
    else
        return min(query(l, tree[o].mid, o<<1), query(tree[o].mid+1, r, (o<<1)+1));
}

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

#include <stdio.h>
#include <algorithm>
using namespace std;
const int maxn = 100010;

int a[maxn];
int d[maxn][maxn];

void rmqinit(int n)
{
    for (int i = 1; i <= n; i++)
        d[i][0] = a[i];
    for (int j = 1; (1<<j) <= n; j++)
    {
        for (int i = 1; i+j-1 <= n; i++)
            d[i][j] = min(d[i][j-1], d[i+(1<<(j-1))][j-1]);
    }
}

int rmq(int l, int r)
{
    int k = 0;
    while ((1<<(k+1)) <= r-l+1) k++;
    return min(d[l][k], d[r-(1<<k)+1][k]);
}

int main()
{
    int t, n, m, l, r;
    scanf("%d",&t);
    for (int k = 1; k <= t; k++)
    {
        scanf("%d%d",&n, &m);
        for (int i = 1; i <= n; i++)
            scanf("%d",&a[i]);
        rmqinit(n);
        printf("Case %d:\n",k);
        while (m--)
        {
            scanf("%d %d",&l, &r);
            printf("%d\n",rmq(l, r));
        }
    }
    return 0;
}