[정올 3239] 구간의 최소값

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&code=3239 

JUNGOL

#include <stdio.h>

//Segment Tree
typedef long long LL;
int N, M;
const int TLM = 1 << 22, LM = 1 << 20, INF = (int)21e8;

struct Segment {
	LL rawdata[LM];
	int minT[TLM]; //rawdata의 idx를 저장
	inline int min(int a, int b) { 
		if (rawdata[a] > rawdata[b]) return b;
		else if (rawdata[a] == rawdata[b]) return a > b ? b : a;
		else return a;
	}
	void init(int now, int s, int e) {
		minT[now] = N + 1;
		if (s >= e) return;
		int lch = now * 2, rch = lch + 1;
		int m = (s + e) / 2;
		init(lch, s, m);
		init(rch, m + 1, e);
	}
	void update(int now, int s, int e, int tg) {
		if (s == e) {//leaf
			minT[now] = tg;
			return;
		}
		int lch = now * 2, rch = lch + 1;
		int m = (s + e) / 2;
		if (tg <= m) update(lch, s, m, tg);
		else update(rch, m + 1, e, tg);
		minT[now] = min(minT[lch], minT[rch]);
	}
	int query(int now, int s, int e, int si, int ei) {
		if (e < si || ei < s) return N + 1;
		if (si <= s && e <= ei) return minT[now];
		int lch = now * 2, rch = lch + 1, m = (s + e) / 2;
		int li = query(lch, s, m, si, ei);
		int ri = query(rch, m + 1, e, si, ei);
		return min(li, ri);
	}
}seg;

int main(void) {
	//freopen("input.txt", "r", stdin);
	scanf("%d%d", &N, &M);
	int i, cmd, a, b;
	seg.rawdata[N + 1] = INF;
	seg.init(1, 1, N);
	for (i = 1; i <= M; i++) {
		scanf("%d%d%d", &cmd, &a, &b);
		if (cmd == 1) { //입력
			seg.rawdata[a] = b;
			seg.update(1, 1, N, a);
		}
		else {
			int mini = seg.query(1, 1, N, a, b);
			if (cmd == 2) {
				if (seg.rawdata[mini] != INF) printf("%d\n", mini);
			}
			else { //cmd == 3
				if (mini <= N) { //만약 전부 INF라면 mini가 N+1로 리턴될 것, 그러면 N+1로는 update 실패한다.
					seg.rawdata[mini] = INF;
					seg.update(1, 1, N, mini);
				}
			}
		}
	}
    return 0;
}