BOJ 백준 30512 조용히 완전히 영원히

문제 : https://www.acmicpc.net/problem/30512

 

 

[ 문제 요약 ]

• 초깃값이 주어지고, 쿼리가 주어집니다. 쿼리에는 L, R 구간 범위와 숫자 X가 주어지고, 이는 배열의 구간의 원소들에 대해 min(원소, X)를 진행합니다.
• 출력은 모든 쿼리를 실행 후의 결과 배열을 출력하고, 각 쿼리당 잊힌 원소의 개수를 출력합니다.
• 잊힌 원소의 개수는 쿼리마다 자기 쿼리 이후 아무 변경 없는 원소들에 대한 개수입니다.

 

[ 테스트 케이스 설명 ]

10// 노드 수 1<=100,000
10 5 6 9 2 4 7 1 8 3// 정수 0<=1,000,000
5// 쿼리 수 1<=100,000
1 2 8// L, R, X(0<=1,000,000)
2 4 6
5 9 4
8 10 1
3 6 7
//쿼리 수행 후 총 결과와, 각 업데이트당 잊힌 원소 개수 출력
8 5 6 6 2 4 4 1 1 1
6 7 8 10 10

 

 

[ 알고리즘 분류 ]

• 자료 구조
• 세그먼트 트리
• 느리게 갱신되는 세그먼트 트리
• 오프라인 쿼리

 

[ 문제 해설 ]

느리게 갱신되는 세그먼트 트리 문제로, 지연 구간 업데이트 알고리즘을 사용합니다.

 

세그먼트 트리마다 노드의 값과, 마지막으로 영향을 미친 노드를 갖고 있도록 합니다.

 

지연 전파 함수 작성 시, 값이 작아질 때마다 값 갱신 및 마지막으로 영향을 미친 쿼리를 갱신하도록 하면 됩니다.

 

출력해 줄 때는 쿼리에 모든 원소에 대해 하나하나 출력하면서, 그때 영향을 미친 쿼리의 개수를 카운팅 합니다.

 

이렇게 하면 영향을 미친 쿼리 개수를 누적 합했을 때, 최종적으로 잊힌 원소의 개수를 확인할 수 있습니다.

 

[ 정답 코드 ]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Main{

	static final int MAX = 1<<30;
	static int N, Q;
	static int arr[];
	static Node lazy[];
	static Node tree[];
	
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		arr = new int[N + 1];
		tree = new Node[N * 4];
		lazy = new Node[N * 4];
		
		for(int i=0; i<tree.length; i++)
		{
			tree[i] = new Node(MAX,0);
			lazy[i] = new Node(MAX,0);
		}
		
		st = new StringTokenizer(br.readLine());
		for(int i=1; i<=N; i++)
			arr[i] = Integer.parseInt(st.nextToken());
		
		init(1, 1, N);
		
		Q = Integer.parseInt(br.readLine());
		for(int i=1; i<=Q; i++)
		{
			st = new StringTokenizer(br.readLine());
			int L = Integer.parseInt(st.nextToken());
			int R = Integer.parseInt(st.nextToken());
			int X = Integer.parseInt(st.nextToken());//(0<=1,000,000)
			update(1, 1, N, L, R, X, i);
		}
		
		StringBuilder sb = new StringBuilder();
		
		int prefixSum[] = new int[Q + 1];
		for(int i=1; i<=N; i++)
		{
			Node now = query(1, 1, N, i);// 원소마다 값을 꺼내옴
			prefixSum[now.lastQuery] += 1;// 꺼내온 값의 마지막 영향을 받은 쿼리 개수 추가
			sb.append(now.num).append(' ');// 최종 결과값 입력
		}
		
		sb.append('\n');
		// 쿼리마다 돌면서 첫번 째 쿼리부터 마지막 쿼리까지 몇번 영향을 미쳤는지 출력
		for(int i=1; i<=Q; i++)
			sb.append(prefixSum[i] += prefixSum[i-1]).append(' ');
		
		System.out.print(sb);
	}
	static Node query(int treeNode, int s, int e, int targetIdx) {
		propagate(treeNode, s, e);
		
		if(s == e)
			return tree[treeNode];
		
		int mid = (s + e) >> 1;
		
		if(targetIdx <= mid)
			return query(treeNode << 1, s, mid, targetIdx);
		
		return query(treeNode << 1 | 1, mid + 1, e, targetIdx);
	}
	static void update(int treeNode, int s, int e, int left, int right, int value, int queryIdx) {
		propagate(treeNode, s, e);
		
		if(e < left || right < s)
			return;
		
		if(left <= s && e <= right)
		{
			lazy[treeNode].num = value;
			lazy[treeNode].lastQuery = queryIdx;
			propagate(treeNode, s, e);
			return;
		}
		
		int mid = (s + e) >> 1;
		
		update(treeNode << 1, s, mid, left, right, value, queryIdx);
		update(treeNode << 1 | 1, mid + 1, e, left, right, value, queryIdx);
	}
	static void propagate(int treeNode, int s, int e) {
		if(lazy[treeNode].lastQuery != 0)
		{
			int num = lazy[treeNode].num;
			int lastQuery = lazy[treeNode].lastQuery;
			
			if(tree[treeNode].num > num)
			{
				tree[treeNode].num = num;
				tree[treeNode].lastQuery = lastQuery;
			}
			
			if(s != e)
			{
				int left = treeNode << 1;
				int right = treeNode << 1 | 1;
				
				if(lazy[left].num > num)
				{
					lazy[left].num = num;
					lazy[left].lastQuery = lastQuery;
				}
				if(lazy[right].num > num)
				{
					lazy[right].num = num;
					lazy[right].lastQuery = lastQuery;
				}
			}
			lazy[treeNode].num = MAX;
			lazy[treeNode].lastQuery = 0;
		}
	}
	static void init(int treeNode, int s, int e) {
		if(s == e)
		{
			tree[treeNode].num = arr[s];
			return;
		}
		
		int mid = (s + e) >> 1;
		
		init(treeNode << 1, s, mid);
		init(treeNode << 1 | 1, mid + 1, e);
	}
	static class Node{
		int num,lastQuery;
		Node(int n, int l){
			num = n;
			lastQuery = l;
		}
	}
}