AOJ Range Minimum Query (RMQ)

問題

Range Minimum Query (RMQ) | Aizu Online Judge

解説

一般的なRMQの問題です。 セグメント木で実装すれば構いません。

コード

#include <iostream>
#define ll long long
using namespace std;

const int INF = (1<<31)-1, MAX_N = 1<<17;

int N, dat[2*MAX_N -1];

void init( int n_ )
{
    N = 1;
    while( N < n_ )
        N <<= 1;
 
    for(int i=0; i < 2*N-1; i++)
        dat[i] = INF;
 
    return;
}
 

void update(int k, int a){
    k += N - 1;
    dat[k] = a;
    while(k > 0){
        k = ( k - 1 ) / 2;
        dat[k] = min(dat[ k * 2 + 1 ], dat[ k * 2 + 2 ]);
    }
    return;
}

int query(int a, int b, int k, int l, int r){
    if( r <= a || b <= l ){
        return INF;
    }
    if( a <= l && r <= b ){
        return dat[k];
    }else{
        int vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
        int vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
        return min(vl, vr);
    }
}

int main(void){
    int n, q;
    
    cin >> n >> q;
    init(n);
    
    for(int i=0; i<q; i++){
        ll com, x, y;
        cin >> com >> x >> y;
        
        if(com == 0){
            update(x, y);
        }else{
            cout << query(x, y+1, 0, 0, N) << endl;
        }
    }
    return 0;
}