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

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

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

Median 2

問題に戻る

解説

먼저 접두사 기록 AAA만 생각하자. 다음과 같이 X1,X2,⋯ ,XNX_1,X_2,\cdots,X_NX1​,X2​,⋯,XN​을 정의한다.

Xi={Ai/2(i가 홀수),Ai−Xi−1(i가 짝수).X_i=\begin{cases} A_i/2 & (i\text{가 홀수}),\\ A_i-X_{i-1} & (i\text{가 짝수}). \end{cases}Xi​={

홀수 iii에서 AiA_iAi​가 홀수이거나, 어떤 XiX_iXi​가 111 이상 이하가 아니라면 불가능하다.

i=2k−1i=2k-1i=2k−1일 때 XiX_iXi​는 앞의 iii개 원소의 중앙값이다. 여기에 Pi+1P_{i+1} 하나를 추가하면 기존 중앙값은 크기가 인 새 집합의 가운데 두 원소 중 하나로 남는다. 따라서 짝수 에서 가운데 두 원소는 정확히 과 이다.

이 사실로 각 위치 iii에서 PiP_iPi​가 들어갈 수 있는 구간 CiAC_i^ACiA​를 얻을 수 있다. 이면 이다. 짝수 에서 , 라 하면, 일 때 , 일 때 이다. 이면 서로 다른 두 가운데 원소가 같아지므로 불가능하다.

홀수 i≥3i\ge 3i≥3에서는 직전 짝수 접두사의 가운데 두 원소를 l<ul<ul<u라 하자. 새 중앙값 XiX_iXi​는 [l,u][l,u]에 있어야 한다. 이면 , 이면 , 이면 이어야 한다. 따라서 는 항상 하나의 정수 구간이다.

위치에 대한 조건만으로는 충분하지 않다. XiX_iXi​는 시점 iii까지 실제로 등장해야 하므로 pos⁡(Xi)≤i\operatorname{pos}(X_i)\le ipos(Xi​)이다. 또한 짝수 에서 가운데 두 원소가 라면, 과 사이의 값은 그 시점까지 하나도 등장할 수 없다. 따라서 모든 에 대해 이다. 이 조건들을 모으면 각 값 에 대해 접두사 기록이 주는 위치 구간 를 얻는다.

접두사 조건의 충분성

위 조건들은 필요조건일 뿐 아니라 충분조건이다. iii를 증가시키며 귀납하자. 홀수 크기의 접두사에서 중앙값이 ccc이고 다음 짝수 시점의 다른 가운데 값이 q<cq<cq<c라고 하자. qqq는 deadline 조건 때문에 이미 등장했고, qqq와 사이의 모든 값은 release 조건 때문에 아직 등장하지 않았다. 따라서 는 현재 바로 아래의 원소이다. 새 값 를 추가하면 가운데 두 원소가 정확히 가 된다. 도 대칭적이다.

접미사 기록 BBB도 오른쪽에서 왼쪽으로 같은 처리를 한다. 접미사 길이 N−i+1N-i+1N−i+1의 홀짝에 따라

Yi={Bi/2(N−i+1이 홀수),Bi−Yi+1
Ai​/2
Ai​−Xi−1​
​
(i가 홀수),(i가 짝수).​
NNN
Pi+1​
2k2k2k
iii
Xi−1X_{i-1}Xi−1​
XiX_iXi​
i=1i=1
i=1
P1=X1P_1=X_1P1​=X1​
iii
c=Xi−1c=X_{i-1}c=Xi−1​
q=Xiq=X_iq=Xi​
q<cq<cq<c
Pi≤qP_i\le qPi​≤q
q>cq>cq>c
Pi≥qP_i\ge qPi​≥q
q=cq=cq=c
[l,u]
Xi=lX_i=lXi​=l
Pi<lP_i<lPi​<l
Xi=uX_i=uXi​=u
Pi>uP_i>uPi​>u
l<Xi<ul<X_i<ul<Xi​<u
Pi=XiP_i=X_iPi​=Xi​
CiAC_i^ACiA​
≤
i
iii
l<ul<ul<u
lll
uuu
l<v<ul<v<ul<v<u
pos⁡(v)≥i+1\operatorname{pos}(v)\ge i+1pos(v)≥i+1
vvv
LvA≤pos⁡(v)≤RvAL_v^A\le \operatorname{pos}(v)\le R_v^ALvA​≤pos(v)≤RvA​
cc
c
qqq
ccc
Pi≤qP_i\le qPi​≤q
q,cq,cq,c
q>cq>cq>c

짝수 크기의 접두사에서 가운데 두 원소가 l<ul<ul<u라면 둘 사이에는 이미 등장한 값이 없다. 다음 중앙값이 내부의 값이면 그 값을 직접 추가해야 하고, 끝점이면 반대쪽 바깥에 값을 하나 추가한다. 앞에서 만든 CiAC_i^ACiA​가 정확히 이 세 경우를 나타낸다. 따라서 모든 접두사 중앙값이 주어진 기록과 일치한다.

(N−i+1이 짝수)Y_i=\begin{cases} B_i/2 & (N-i+1\text{이 홀수}),\\ B_i-Y_{i+1} & (N-i+1\text{이 짝수}) \end{cases}
Yi​={Bi​/2Bi​−Yi+1​​(N−i+1이 홀수),(N−i+1이 짝수)​

로 둔다. 같은 논리로 위치 iii의 값 구간 CiBC_i^BCiB​와 값 vvv의 위치 구간 LvB≤pos⁡(v)≤RvBL_v^B\le \operatorname{pos}(v)\le R_v^BLvB​≤pos(v)≤RvB​를 얻는다. 이번에는 YiY_iYi​가 접미사에 등장해야 하므로 pos⁡(Yi)≥i\operatorname{pos}(Y_i)\ge ipos(Yi​)≥i이고, 짝수 길이 접미사의 가운데 두 값 l<ul<ul<u 사이의 값들은 그 접미사에 없어야 하므로 pos⁡(v)≤i−1\operatorname{pos}(v)\le i-1pos(v)≤i−1이다.

두 방향의 조건을 합치면 각 위치에는 하나의 값 구간 ℓi≤Pi≤ri\ell_i\le P_i\le r_iℓi​≤Pi​≤ri​가 생기고, 각 값에는 하나의 위치 구간 Lv≤pos⁡(v)≤RvL_v\le \operatorname{pos}(v)\le R_vLv​≤pos(v)≤Rv​가 생긴다. 구간의 교집합이 비어 있으면 즉시 불가능하다.

이제 왼쪽부터 위치 i=1,2,⋯ ,Ni=1,2,\cdots,Ni=1,2,⋯,N을 채운다. Lv=iL_v=iLv​=i가 된 값 vvv를 활성화한다. 활성화되어 아직 사용되지 않은 값 중 ℓi≤v≤ri\ell_i\le v\le r_iℓi​≤v≤ri​를 만족하는 값만 현재 위치에 놓을 수 있다. 그중 RvR_vRv​가 가장 작은 값을 선택한다.

이 그리디에는 다음 교환 성질이 성립한다. 현재 위치 iii에서 어떤 완성 가능한 답이 값 ppp를 사용하고, 그리디가 값 qqq를 골랐다고 하자. 그 답에서 qqq가 놓인 위치를 j≥ij\ge ij≥i라 하자. 그리디의 선택으로 Rq≤RpR_q\le R_pRq​≤Rp​이다. qqq가 jjj에 놓일 수 있으므로 j≤Rqj\le R_qj≤Rq​, 따라서 j≤Rpj\le R_pj≤Rp​이고 Lp≤i≤jL_p\le i\le jLp​≤i≤j도 성립한다.

남는 것은 위치 jjj의 값 구간이다. 중앙값 기록에서 만들어지는 구간에는 다음 성질이 있다. i<ji<ji<j이고 두 값이 모두 위치 iii에서 가능하며, 그중 qqq는 위치 jjj에서도 가능한데 ppp는 불가능하다면 Rp<RqR_p<R_qRp​<Rq​이다. 이를 확인하려면 CiA,CiBC_i^A,C_i^BCiA​,CiB​가 변하는 세 경우만 보면 된다. 한 경계가 ppp와 qqq 사이를 지나 ppp만 제외하는 최초의 순간에는, ppp가 접두사의 가운데 값으로 확정되어 그 시점까지 등장해야 하거나, ppp가 짝수 길이 접미사의 두 가운데 값 사이에 들어가 그 시점 이전에 등장해야 한다. 두 경우 모두 그 순간이 RpR_pRp​를 결정한다. 반면 qqq는 그 뒤의 위치 jjj에서도 가능하므로 Rq≥jR_q\ge jRq​≥j이다. 따라서 Rp<RqR_p<R_qRp​<Rq​이다.

지금은 Rq≤RpR_q\le R_pRq​≤Rp​이므로 위 상황은 일어날 수 없다. 따라서 ppp도 위치 jjj에 놓을 수 있다. 답에서 ppp와 qqq를 교환하면 그리디의 첫 선택을 포함하는 완성 가능한 답을 얻는다. 이를 반복하면 그리디가 실패하지 않는 한 항상 전체 순열을 완성할 수 있다.

구현에서는 열린 값 구간에 대한 LvAL_v^ALvA​의 range chmax와 RvBR_v^BRvB​의 range chmin이 필요하다. 모든 갱신이 끝난 뒤 점 값만 필요하므로 lazy 값만 저장하는 세그먼트 트리로 각각 O(Nlog⁡N)O(N\log N)O(NlogN)에 처리할 수 있다.

마지막 그리디에서는 값 vvv를 좌표 vvv에 두고, 활성화된 값의 리프에 (Rv,v)(R_v,v)(Rv​,v)를 저장하는 세그먼트 트리를 사용한다. 위치 iii에서 [ℓi,ri][\ell_i,r_i][ℓi​,ri​]의 최소 쌍을 구하면 바로 선택할 값을 얻는다. 트리 전체의 최소 deadline이 iii보다 작아졌다면 이미 놓을 수 없는 값이 생긴 것이므로 불가능하다.

구성이 끝난 뒤 만들어진 순열의 모든 접두사와 접미사 중앙값을 Fenwick tree의 kkk번째 원소 탐색으로 다시 확인할 수 있다. 잘못된 입력에 대한 구현상 검산으로 사용할 수 있으며 복잡도는 그대로 O(Nlog⁡N)O(N\log N)O(NlogN)이다.

시간 복잡도는 O(Nlog⁡N)O(N\log N)O(NlogN), 메모리 복잡도는 O(N)O(N)O(N)이다.

Solution written by GPT5.6