[C/C++] 백준 - 수열과 쿼리 문제

 

 

✏️ 문제 링크

https://www.acmicpc.net/problem/14438

14438번: 수열과 쿼리 17

 

✏️ 문제 설명

 

 

✏️ 문제 코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

#define INF 1000000001
vector<int>tree,arr;
int initTree(int start, int end, int node);
int updateTree(int start, int end, int node, int index);
int findMin(int start, int end, int node, int left, int right);
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N,M,Q,index,value,left,right;
	cin >> N;
	arr.resize(N);
	tree.resize(N * 4);

	for (int i = 0; i < N; i++)
		cin >> arr[i];

	initTree(0, N - 1, 1);
	cin >> M;
	
	for (int i = 0; i < M; i++) {
		cin >> Q;
		if (Q == 1) {
			cin >> index >> value;
			arr[index - 1] = value;
			updateTree(0, N - 1, 1,index - 1);
		}
		else {
			cin >> left >> right;
			cout << findMin(0, N - 1, 1, left - 1, right - 1) << '\n';
		}
	}


}
int initTree(int start, int end, int node) {
	if (start == end)
		return tree[node] = arr[start];
	int mid = (start + end) / 2;
	int leftmin = initTree(start, mid, node * 2);
	int rightmin = initTree(mid + 1, end, node * 2 + 1);
	if (leftmin < rightmin)
		return tree[node] = leftmin;
	else
		return tree[node] = rightmin;
}
int updateTree(int start, int end, int node, int index) {
	if (index<start || index>end)
		return tree[node];
	if (start == end)
		return tree[node] = arr[index];
	int mid = (start + end) / 2;
	int leftmin = updateTree(start, mid, node * 2, index);
	int rightmin = updateTree(mid + 1, end, node * 2 + 1, index);
	return tree[node] = min(leftmin, rightmin);
}
int findMin(int start, int end, int node, int left, int right) {
	if (left > end || right < start)
		return INF;
	if (left <= start && right >= end)
		return tree[node];
	int mid = (start + end) / 2;
	int leftmin = findMin(start, mid, node * 2, left, right);
	int rightmin = findMin(mid + 1, end, node * 2 + 1, left, right);
	return min(leftmin, rightmin);

}

 

 

 

✏️ 문제 링크

https://www.acmicpc.net/problem/14428

14428번: 수열과 쿼리 16

 

 

✏️ 문제 설명

 

 

✏️ 문제 코드

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> Arr, Tree;

int initTree(int Begin, int End, int Node) {
    if(Begin == End) return Tree[Node] = Begin;
    int Mid = (Begin+End)/2;
    int leftMinIdx = initTree(Begin, Mid, Node*2);
    int rightMinIdx = initTree(Mid+1, End, Node*2+1);
    if(Arr[leftMinIdx] < Arr[rightMinIdx]) return Tree[Node] = leftMinIdx;
    else if(Arr[leftMinIdx] > Arr[rightMinIdx]) return Tree[Node] = rightMinIdx;
    else return Tree[Node] = min(leftMinIdx, rightMinIdx);
}

int updateTree(int Begin, int End, int Node, int Index) {
    if(Index < Begin || Index > End || Begin == End) return Tree[Node];
    int Mid = (Begin+End)/2;
    int leftMinIdx = updateTree(Begin, Mid, Node*2, Index);
    int rightMinIdx = updateTree(Mid+1, End, Node*2+1, Index);
    if(Arr[leftMinIdx] < Arr[rightMinIdx]) return Tree[Node] = leftMinIdx;
    else if(Arr[leftMinIdx] > Arr[rightMinIdx]) return Tree[Node] = rightMinIdx;
    else return Tree[Node] = min(leftMinIdx, rightMinIdx);
}

int findMinIdx(int Begin, int End, int Node, int Left, int Right) {
    if(Left > End || Right < Begin) return -1;
    if(Left <= Begin && Right >= End) return Tree[Node];
    int Mid = (Begin+End)/2;
    int leftMinIdx = findMinIdx(Begin, Mid, Node*2, Left, Right);
    int rightMinIdx = findMinIdx(Mid+1, End, Node*2+1, Left, Right);
    if(leftMinIdx < 0) return rightMinIdx;
    if(rightMinIdx < 0) return leftMinIdx;
    if(Arr[leftMinIdx] < Arr[rightMinIdx]) return leftMinIdx;
    else if(Arr[leftMinIdx] > Arr[rightMinIdx]) return rightMinIdx;
    else return min(leftMinIdx, rightMinIdx);
}

int main() {
    int N, M, Q, Index, Value, Left, Right;
    scanf("%d", &N);
    Arr.resize(N);
    for(int i=0; i<N; i++) scanf("%d", &Arr[i]);
    Tree.resize(N*4);
    initTree(0, N-1, 1);
    scanf("%d", &M);
    for(int i=0; i<M; i++) {
        scanf("%d", &Q);
        if(Q == 1) {
            scanf("%d %d", &Index, &Value);
            Arr[Index-1] = Value;
            updateTree(0, N-1, 1, Index-1);
        }
        else {
            scanf("%d %d", &Left, &Right);
            printf("%d\n", findMinIdx(0, N-1, 1, Left-1, Right-1)+1);
        }
    }
}

 

 

 

✏️ 문제 링크

https://www.acmicpc.net/problem/14427

14427번: 수열과 쿼리 15

 

 

✏️ 문제 설명

 

 

✏️ 문제 코드

#include<iostream>
#include<vector>
using namespace std;

vector<int>tree, arr;
int initTree(int start, int end, int node);
int updateTree(int start, int end, int index,int value);
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M, Q, index, value;
	cin >> N;
	tree.resize(N*4);
	arr.resize(N);
	for (int i = 0; i < N; i++)
		cin >> arr[i];

	initTree(0, N - 1, 1);
	cin >> M;

	for (int i = 0; i < M; i++) {
		cin >> Q;
		if (Q == 1) {
			cin >> index >> value;
			arr[index - 1] = value;
			updateTree(0, N - 1, 1,index-1 );
		}
		else {
			cout << tree[1]+1 << "\n";
		}
	}

}
int initTree(int start, int end, int node) {
	if (start == end)
		return tree[node] = start;
	int mid = (start + end) / 2;
	int left = initTree(start, mid, node * 2);
	int right = initTree(mid + 1, end, node * 2 + 1);
	if (arr[left] > arr[right])
		return tree[node] = right;
	else if (arr[left] < arr[right])
		return tree[node] = left;
	else
		return tree[node] = min(left, right);
}
int updateTree(int start, int end, int node, int index) {
	if (index<start || index>end||start==end)
		return tree[node];
	int mid = (start + end) / 2;
	int left = updateTree(start, mid, node * 2, index);
	int right = updateTree(mid + 1, end, node * 2 + 1, index);
	if (arr[left] < arr[right])
		return tree[node] = left;
	else if (arr[right] < arr[left])
		return tree[node] = right;
	else
		return tree[node] = min(left, right);
}

 

기존에 풀던 세그먼트 트리 구현 방식으로는 시간 초과가 나서

https://restudycafe.tistory.com/

복습 정리 노트

이분 껄 참고해서 풀었습니다