https://atcoder.jp/contests/ddcc2020-final/tasks/ddcc2020_final_c
本番はさんざんでしたが…良問です。
実はiにおける答えはi
見れば良いです。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"; } }