모스 알고리즘의 기본 원리와 구현
구간 내 서로 다른 숫자의 개수를 효율적으로 계산하는 문제를 고려해 보겠습니다. 단순한 접근은 매번 좌우 끝점을 이동하며 답을 갱신하는 것이지만, 이 방식은 O(n²) 시간이 소요됩니다. 모스 알고리즘은 이 문제를 효율적으로 해결하기 위해 고안되었습니다.
모스 알고리즘은 쿼리를 오프라인으로 처리하고 블록 기반 정렬을 적용합니다. 배열을 √n 크기의 블록으로 ...
6월 4일 17:01에 게시됨
세그먼트 트리의 기본 연산과 구현
단일 요소 수정 및 구간 질의
기본적인 세그먼트 트리는 이진 트리 구조로 단일 요소 수정과 구간 질의를 지원합니다:
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_N = 200010;
struct TreeNode {
int left, right, max_val;
} tree[MAX_N * 4];
void update_node(int idx) {
tree[idx].max_val = max(tree[idx*2 ...
6월 1일 04:21에 게시됨