DISCO presents ディスカバリーチャンネル コードコンテスト2020 本戦C: Smaller-Suffix-Free Sequences

https://atcoder.jp/contests/ddcc2020-final/tasks/ddcc2020_final_c

本番はさんざんでしたが…良問です。

実はiにおける答えはiS[j...N]を満たす最小のindexです。つまり、suffix array順でiがjの後に来るものを
見れば良いです。O(NlogN)となります。

証明はeditorialを参考にしてください。

suffix arrayを使うのが本質だと思ってしまい、ずっとsuffix arrayをこねくり回してしまったのが敗北原因です。ちゃんと条件を整理しに行く必要が有りました。
algorithmな解法は最後まで取っておくのが吉です。

あとsuffix arrayの使い方を忘れてしまったのも良くなかったです。文字の種類数を200000とかにしたら壊れるかなと思ったんですが壊れません。SA-ISすごいね。

int N;
vi vec;
int ans[MAX_N];
int I[MAX_N];

void solve() {
	cin >> N;
	vec.resize(N);
	rep(i, 0, N) {
		cin >> vec[i];
		vec[i]--;
	}
	SA sa; sa.init(vec, 200000);
	rep(i, 1, N + 1) {
		I[sa.sa[i]] = i - 1;
	}
	// debug(vi(I, I + N));
	segtree seg; seg.init(N);
	rer(i, N, 0) {
		int v = seg.get(0, I[i]).v;
		ans[i] = min(v, N);
		seg.update(I[i], I[i] + 1, i);
	}
	rep(i, 0, N) {
		cout << ans[i] << "\n";
	}
}