DOJ logoDOJ
問題
最近追加された問題保存した問題Workbooks
カテゴリDLCコンテストグループチーム掲示板
ランキング
正解数ランキングストリークランキングDOJ Powerランキング
提出状況
問題募集ログイン新規登録
DOJ logoDOJ

OI形式のサブタスク採点、Eloレーティング、Discord連携を備えたオンラインジャッジです。

問題
問題一覧カテゴリ
コミュニティ
コンテストランキング掲示板お知らせ外部のコンテストを開催するガイド
アカウント
ログイン新規登録ジャッジ状態
ポリシー
利用規約DLCの利用規則プライバシーAPI 文書言語ランタイムコンテストの順位報酬レーティングとパフォーマンス
© 2026 DOJ
All rights reserved
解説

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