RMQ 문제 풀이: 슈퍼 피아노, 빈도 값, 인구 조사 문제
P2048 [NOI2010] 슈퍼 피아노
연속 부분 수열의 합을 전처리하고 RMQ를 사용하여 최대값을 찾습니다.
우선순위 큐를 사용하여 최적의 답을 저장합니다.
힙의 맨 위 요소를 꺼내서 계산한 후, 해당 지점을 제외하고 두 개의 새로운 구간을 다시 큐에 추가합니다. 이 과정을 k번 반복합니다.
#include <iostream>
#include <vector>
#include <queue>
#inc ...
7월 2일 00:21에 게시됨
Codeforces Round 864 (Div. 2) E. Li Hua and Array
문제 개요
배열의 각 원소에 대해 오일러 함수를 반복적으로 적용하면서, 특정 범위 내의 모든 원소가 동일한 값으로 수렴하는 최소 연산 횟수를 구하는 문제입니다. 이 과정에서 선형 시간 전처리와 세그먼트 트리, 그리고 LCA(Lowest Common Ancestor) 기법을 결합하여 효율적인 쿼리를 처리합니다.
핵심 아이디어
오일러 함수 φ(n)는 정수 n에 대해 1부터 n까지의 자 ...
6월 19일 02:59에 게시됨