DOJ logoDOJ
题目
最近添加的题目收藏的题目Workbooks
分类DLC比赛小组团队讨论区
排名
解题数量排行榜连续解题排名DOJ Power 排行榜
评测状态
征题登录注册
DOJ logoDOJ

支持 OI 子任务计分、Elo 等级分和 Discord 账号绑定的社区在线评测系统。

题目
题目列表分类
社区
比赛排名讨论区公告举办外部比赛指南
账号
登录注册评测状态
政策
服务条款DLC 使用规则隐私政策API 文档语言运行环境比赛排名奖励评级与表现
© 2026 DOJ
保留所有权利
题解

Sliding Window RMQ

返回题目

题解

서브태스크 111에서는 수열을 생성한 뒤 모든 길이 KKK 구간을 직접 훑을 수 있다. 서브태스크 222에서는 크기 KKK의 순환 배열에 새 값을 덮어쓰고 구간 최솟값 세그먼트 트리의 루트 값을 읽으면 된다.

전체 문제에서는 후보 원소의 인덱스를 덱에 저장한다. 맨 앞 원소가 현재 구간에서 벗어나면 제거한다. 새 값 AiA_iAi​를 넣기 전에 덱 뒤에서 AiA_iAi​ 이상인 값들을 모두 제거한다. 새 값을 뒤에 넣으면 덱의 값은 앞에서 뒤로 엄격히 증가하고, 맨 앞이 현재 구간의 최솟값이 된다. 제거된 값은 나중의 어느 구간에서도 새 값보다 유리할 수 없으므로 정답에 영향을 주지 않는다. 각 원소는 덱에 한 번 들어가고 한 번 이하 제거되므로 총 O(N)O(N)O(N) 시간과 O(K)O(K)O(K) 공간을 사용한다.

A0A_0A0​ 자체는 구간에 포함되지 않는다. 곱셈 aAi−1+caA_{i-1}+caAi−1​+c는 32비트 범위를 넘으므로 64비트 정수로 계산한다.

Solution written by GPT6