公式の解説に載ってなかったので。
まず、優先度つきキューなどに、配列Aに含まれていない要素（MEXになりうる数）を入れます。
優先度つきキューは、入っている要素の中の最小値を高速で取り出すことができるので、これでMEXを高速で求めることができます。
また、multisetなどに、配列Aをそのまま入れます。
その後はimos法の要領で、multisetなどにどんどん要素を追加したり削除したりします。
その時は、multisetをいい感じに操作します。
まず、削除する時は、multisetから一つだけ削除します。そして、multisetに含まれているその要素の数がもし0になった場合は、優先度つきキューにその要素を入れます。
追加するときは、multisetに追加するだけで優先度つきキューには何の操作もしません
これでは、ただ優先度つきキューから最小値を取り出してもただしいMEXにならない場合があるので、ちゃんと工夫をします。
MEXを求める時、優先度つきキューから最小値を取り出しますが、もしそれがmultisetに含まれている場合は優先度つきキューから削除し、もう一回最小値を取り出す…というのをmultisetに含まれていない数値が出るまで繰り返します。
こうしてMEXを求めることができます。
multisetに含まれているかどうかをmultisetで確認すると、いくら平衡二分木でも同じ要素が大量に入っていた時などは実行時間がかかるようなので、判定をする用のsetを用意しておくと通ります。
#include <bits/stdc++.h> using namespace std; int main() { int n,m,hako; cin >> n >> m; vector<int>a(n); for(int i=0;i<n;i++)cin >> a[i]; priority_queue<int,vector<int>,greater<int>>prq; multiset<int>st; set<int>st2; for(int i=0;i<m;i++)st.insert(a[i]),st2.insert(a[i]); for(int i=0;i<n+10;i++)if(st2.count(i)==0)prq.push(i); int ans=1e9; for(int i=m;i<n;i++){ hako=prq.top(); while(st2.count(hako)>0){ prq.pop(); hako=prq.top(); } ans=min(ans,hako); auto itr=st.find(a[i-m]); st.erase(itr); if(st.count(a[i-m])==0)prq.push(a[i-m]),st2.erase(a[i-m]); st.insert(a[i]); st2.insert(a[i]); } hako=prq.top(); while(st2.count(hako)>0){ prq.pop(); hako=prq.top(); } cout << min(ans,hako) << endl; return 0; }
