rmq.cpp

Bài toán

Cho một dãy a gồm N số nguyên, và K cặp số u,v.  (1<=N<=100000, K<=1000000).

Với mỗi cặp số (u,v) hãy in ra số lớn nhất trong khoảng a[u..v].

Độ phức tạp:

khởi tạo : O(n log n)

trả lời truy vấn : O(1)

Vì N, K lớn nên ta phải tìm một thuật toán tối ưu, gọi là RMQ.

Code này của : Nguyễn Tiến Trung Kiên

#include <math.h>

#include <stdio.h>

int a[230997];

int M[230997][23];

int n, m;

int max(int a, int b) { return a > b ? a : b; }

int main() {

    int i, k;

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

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

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

    for (i = 1; i <= n; i++) M[i][0] = a[i];

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

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

            M[i][k] = max(M[i][k - 1], M[i + (1 << (k - 1))][k - 1]);

    int u, v;

    while (m--) {

        scanf("%d%d", &u, &v);

        k = log2(v - u + 1);

        printf("%d\n", max(M[u][k], M[v - (1 << k) + 1][k]));

    }

}

Nhận xét

Dễ hiểu thôi!

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Range_Minimum_Query_%28RMQ%29