백준 25639: 수열과 최대 상승 쿼리

문제 요약

길이가 $N$인 수열 $a_1, a_2, ..., a_N$이 주어졌을 때, 다음과 같은 쿼리를 수행하는 프로그램을 작성해보자.

• 1 k x: $a_k$를 $x$로 바꾼다.
• 2 l r: 구간 $[l, r]$의 최대 상승 값을 출력한다. 구간 $[l, r]$의 최대 상승 값은 다음과 같이 정의한다.
• $\max(a_j-a_i)\ (l\le i\le j \le r)$ 

문제 분류

• 자료 구조
• 세그먼트 트리

문제 풀이

세그먼트 트리인데 요구하는 연산이 심상치가 않다. 구간의 최대 상승값을 구한다는 것은 구간의 최댓값에서 최솟값구하여 그 둘을 뺀 값을 구한다는 것과 같다. 단, 단순히 그 둘을 빼는 것이 아니라 반드시 상대적인 순서로 오른쪽에서 왼쪽의 값을 빼야 한다.
이를 다음과 같이 생각할 수 있다. 세그먼트 트리의 어떤 구간의 최대 상승값은, 그 왼쪽 구간과 오른쪽 구간을 생각하여, 오른쪽 구간의 최댓값에서 왼쪽 구간의 최솟값을 뺀 값을 후보로 생각할 수 있다.
또 다른 후보로는 오른쪽 구간의 최대 상승값, 왼쪽 구간의 최대 상승값이 있다. 이 세 후보의 최댓값이 바로 해당 구간의 최대상승값이 되겠다.

세그먼트 트리를 바텀업 방식으로 구성하여 풀었는데, 이 문제는 탑다운 방식으로 푸는 것이 훨씬 간결하게 풀린다. 왼쪽 구간과 오른쪽 구간의 순서가 중요하므로 리프노드의 개수는 2의 거듭제곱 꼴로 나타나야 하고, 푸는 접근 자체도 탑다운이 더 용이하다고 생각한다.

풀이 코드

import java.util.*;
import java.io.*;

public class Main {	
	static int n, size;
	static Node t[];
	
	static void set(int p, int val) {
		p += size;
		t[p].max = val;
		t[p].min = val;
		t[p].res = 0;
		// update
		while((p >>= 1) > 0) {
			t[p].res = Math.max(t[p << 1 | 1].max - t[p << 1].min,
					Math.max(t[p << 1].res, t[p << 1 | 1].res));
			t[p].max = Math.max(t[p << 1].max, t[p << 1 | 1].max);
			t[p].min = Math.min(t[p << 1].min, t[p << 1 | 1].min);
		}
	}
	
	static int query(int l, int r) {
		int res = -1;
		l += size;
		r += size;
		Node left = new Node(), right = new Node();
		while(l <= r) {
			if((l & 1) > 0) {
				left.res = Math.max(t[l].max - left.min,
						Math.max(left.res, t[l].res));
				left.max = Math.max(left.max, t[l].max);
				left.min = Math.min(left.min, t[l].min);				
				l++;
			}
			if((r & 1) == 0) {
				right.res = Math.max(right.max - t[r].min,
						Math.max(right.res, t[r].res));
				right.max = Math.max(right.max, t[r].max);
				right.min = Math.min(right.min, t[r].min);				
				r--;
			}
			r >>= 1;
			l >>= 1;
		}
		
		res = Math.max(right.max - left.min,
				Math.max(left.res, right.res));
		return res;
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		n = Integer.parseInt(br.readLine());
		
		size = 131072;
		t = new Node[size * 2];
		for(int i = 1; i < size * 2; i++)
			t[i] = new Node();
		
		st = new StringTokenizer(br.readLine());
		int q, a, b;
		for(int i = 0; i < n; i++) {
			q = Integer.parseInt(st.nextToken());
			set(i, q);
		}
		int m = Integer.parseInt(br.readLine());
		while(m-- > 0) {
			st = new StringTokenizer(br.readLine());
			q = Integer.parseInt(st.nextToken());
			a = Integer.parseInt(st.nextToken()) - 1;
			b = Integer.parseInt(st.nextToken());
			if(q == 1)
				set(a, b);
			else
				sb.append(query(a, b - 1)).append("\n");
		}
		System.out.print(sb);
	}
}

class Node {
	int min = 1000000001;
	int max = -1000000001;
	int res = -1;
	Node() {}
	Node(int min, int max, int res) {
		this.min = min;
		this.max = max;
		this.res = res;
	}
}