BZOJ4826 HNOI2017 影魔 문제 풀이
길이가 $N$인 순열 $A$와 두 상수 $p_1, p_2$가 주어진다. 인덱스 쌍 $(i, j)$ ($i < j$)에 대해 다음 조건 중 하나를 만족하면 해당 쌍은 정해진 점수를 기여한다:
조건 1: $j = i + 1$이거나, 구간 $(i, j)$ 내 모든 원소가 $\min(A_i, A_j)$보다 크거나 같으면, 기여도는 $p_1$이다.
조건 2: $\min(A_i, A_j) < \max_{k \in (i,j)} A_k < \max(A_i, A_j)$이면, 기 ...
8월 10일 16:04에 게시됨
지속성 세그먼트 트리
개요
이 자료구조는 여러모로 유용하지만, 코드를 작성하는 것은 다소 복잡합니다. 특히 길이가 매우 길어질 수 있습니다.
기본 지식: 세그먼트 트리
본론
지속성 세그먼트 트리—문자 그대로 해석하면 '주석이 달린 트리'입니다.
지속성 세그먼트 트리는 여러 개의 세그먼트 트리로 구성됩니다(개인적인 이해, 아래 그림 참조).
처음에는 단 한 그루의 세그먼트 트리만 존 ...
7월 26일 21:15에 게시됨
자료구조 문제 풀이 모음
이 문서에서는 다양한 자료구조 문제들을 다루며, 세그먼트 트리, 블록 분할, 그리고 코뜰리 트리(ODT)를 활용한 풀이를 소개한다.
P6812 「MCOI-02」조상 (Ancestor)
문제에서 정의한 "조상"은 비내림차순 수열이다. 이를 판별하기 위해 차분 배열을 활용하여 세그먼트 트리로 구간 최솟값을 관리할 수 있다. 차분 배열의 구간 최솟값이 0 이상이면 해당 구간은 비내림차 ...
6월 12일 16:42에 게시됨
세그먼트 트리의 기본 연산과 구현
단일 요소 수정 및 구간 질의
기본적인 세그먼트 트리는 이진 트리 구조로 단일 요소 수정과 구간 질의를 지원합니다:
#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에 게시됨
AtCoder ABC388 문제 풀이 분석
A - UPC 조합
문제 개요
입력 문자열의 첫 번째 글자 뒤에 "UPC"를 붙여 출력한다.
핵심 아이디어
문자열 인덱싱을 활용한 단순 구현.
구현
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string str;
cin >> str;
cout << str.front() << "UPC" <&l ...
5월 22일 13:43에 게시됨