[백준] 10868 최솟값

문제 주소 : www.acmicpc.net/problem/10868

10868번: 최솟값

문제 확인

 

문제에서 쿼리의 개수가 최대 10만 개 이므로 단순히 계산으로 풀면 시간 초과가 나게 됩니다.

따라서 쿼리에 따른 처리법인 mo's 알고리즘 혹은 세그먼트 트리를 통해 풀 수 있습니다.

처음엔 mo's 알고리즘으로 쿼리를 전처리 후 정렬된 query 순으로 풀어나가는 방법으로 시도하였습니다. 기록해둔 쿼리의 범위가 현재 쿼리의 범위보다 넓은 경우엔 최솟값 갱신을 쉽게 할 수 있지만 반대의 경우엔 어느 위치에 최솟값이 위치하는지 알 수 없으므로 새로 찾아야 하기 때문에 연산 횟수가 많아져 세그먼트 트리를 활용하게 되었습니다.

세그먼트 트리 : latter2005.tistory.com/28

[자료구조] 세그먼트 트리

 

풀이

 

값 갱신이 없으므로 값을 입력받는 즉시 세그먼트 트리 데이터 부분에 저장합니다.

사용한 iterative 세그먼트 트리에서 범위에서 벗어나는 구간을 의미하는 홀수를 이용하여 구간 최솟값을 구해나갑니다.

 

코드

#include <cstdio>
#include <algorithm>
#include <sys/stat.h>
#include <sys/mman.h>
 
class fio {
    size_t rsize;
    unsigned char* rbuf;
    static const int wsize = 0xffff;
    unsigned char wbuf[wsize];
    int ridx, widx;
 
public:
    fio() : ridx(0), widx(0) {
        struct stat rstat;
        fstat(0, &rstat);
        rsize = rstat.st_size;
        rbuf = (unsigned char*)mmap(0, rsize, PROT_READ, MAP_FILE | MAP_PRIVATE, 0, 0);
    }
 
    inline bool isBlank() {
        return
            !(rbuf[ridx] != '\n' && rbuf[ridx] != '\t' && rbuf[ridx] != '\r' &&
            rbuf[ridx] != '\f' && rbuf[ridx] != '\v' && rbuf[ridx] != ' ');
    }
    inline void consumeBlank() { while (isBlank()) ridx++; }
 
    int readInt() {
        int res = 0, flag = 0;
        consumeBlank();
        if (rbuf[ridx] == '-') {
            flag = 1;
            ridx++;
        }
        while (!isBlank() && ridx < rsize)
            res = 10 * res + rbuf[ridx++] - '0';
        return flag ? -res : res;
    }
 
    inline void flush() {
        fwrite(wbuf, 1, widx, stdout);
        widx = 0;
    }
 
    inline int intSize(int x) {
        int cnt = 1;
        x = (x > 0) ? x : -x;
        while (x /= 10) cnt++;
        return cnt;
    }
 
    inline void check(int n) { if (widx + n >= wsize) flush(); }
    inline void writeChar(char z) { check(1); wbuf[widx++] = z; }
 
    void writeInt(int x) {
        int sz = intSize(x);
        check(sz);
        if (x < 0) {
            writeChar('-');
            x = -x;
        }
        for (int i = 1; i <= sz; ++i) {
            wbuf[widx + sz - i] = x % 10 + '0';
            x /= 10;
        }
        widx += sz;
    }
};
using namespace std;
 
int main() {
    fio fo;
    int tree[200002];
    int n = fo.readInt(), m = fo.readInt();
    for (int i = 0; i < n; i++)
        tree[n + i] = fo.readInt();//입력
    for (int i = n - 1; i > 0; i--)
        tree[i] = min(tree[i << 1], tree[i << 1 | 1]);//트리 생성
    while (m--) {
        int s = fo.readInt(), e = fo.readInt(), mn = 0x7fffffff;
        for (s += n - 1, e += n; s < e; s >>= 1, e >>= 1) {
            if (s & 1) mn = min(tree[s++], mn);//왼쪽 벗어나는 범위
            if (e & 1) mn = min(tree[--e], mn);//오른쪽 벗어나는 범위
        }
        fo.writeInt(mn);
        fo.writeChar('\n');
    }
    fo.flush();
}