AtCoder ABC #299 (東京海上日動プログラミングコンテスト2023) : G - Minimum Permutation

前半からしてグダグダすぎた…。
https://atcoder.jp/contests/abc299/tasks/abc299_g

問題

N要素の整数列Aが与えられる。
Aには、1～Mの値がそれぞれ最低1個は含まれている。

Aの部分列として得られる1～MのPermutation Pのうち、辞書順最低のものを答えよ。

解法

Aの先頭から見て行って、解となるPermutationに残すかどうかを逐次判定していく。
今A[i]を見ているとき、判定基準は以下。

• A[i]未満の値でまだPに含んでいないものについて、それぞれA中で登場する最寄のindexのうち最小値をXとする。
• A[i]以上の値でまだPに含んでいないものについて、それぞれA中で登場する最後のindexのうち最小値をYとする。

X＜Yの場合、今ここでA[i]をPに入れないことで、Pにもっと小さい値を先に入れられるので、A[i]をPに入れない。
X＞Yの場合、今ここでA[i]をPに入れないことで、Pにもっと大きな値を先に入れられるので、A[i]をPに入れる。

int N,M;
int A[202020];
deque<int> Q[202020];
int did[202020];

template<class V,int NV> class SegTree_mi {
public:
	vector<V> val;
	static V const def=1<<20;
	V comp(V l,V r){ return min(l,r);};
	
	SegTree_mi(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=v;
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};

SegTree_mi<int,1<<20> stmi1,stmi2;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>A[i];
		Q[A[i]].push_back(i);
	}
	FOR(i,M) {
		stmi1.update(i+1,Q[i+1][0]);
		stmi2.update(i+1,Q[i+1].back());
	}
	vector<int> R;
	FOR(i,N) {
		x=A[i];
		if(did[x]) continue;
		
		if(Q[x].size()==1) {
			R.push_back(x);
			did[x]=1;
			stmi1.update(x,1<<20);
			stmi2.update(x,1<<20);
			continue;
		}
		
		Q[x].pop_front();
		stmi1.update(x,Q[x][0]);
		
		int y=stmi1.getval(0,x);
		int k=stmi2.getval(x,M+1);
		if(y>k) {
			R.push_back(x);
			did[x]=1;
			stmi1.update(x,1<<20);
			stmi2.update(x,1<<20);
		}
	}
	FORR(r,R) cout<<r<<" ";
	cout<<endl;
}

まとめ

本番は判定条件を微妙にミスってWAを繰り返してしまった。